Algorithms and Data Structures
Execrcise 4
Recursion

Question 1 [PostScript for printing]

(1) Wirite recurrence formulas for the following sequences.

(2) Consider the following function rule() below which uses a function mark(). mark() draws a line to the rule. For example, mark( 13, 3 ) draws a line of height 3 in the position 13. Illustrate in sequential order how the linse are drawn, when rule( 4, 12, 3) is executed.

void rule(int left, int right, int height){
  int middle = (left+right)/2;
  if( height>0 ){
    mark(middle, height);
    rule(middle, right, height-1);
    rule(left, middle, height-1);
  }
}

The following equation is an example of recurrence formula for an arithmetic sequeence with the first term equal to 1 and with the difference equal to 1 f(n) = n + (n-1) + ... + 2 + 1
f(n)=n+f(n-1),f(0)=0

The Horner method is a method of expanding the higher order polynomial in the form of (ax + b). For example, f(x) = 1x4 + 2x3 + 3x2 + 4x + 5
is expanded by the Horner method as follows
Horner method

The following figure is an example of line drawn by mark(13,3)< br /> mark(13,3)

Question 2

Write the C-functions which perfrom the calculations specified below using recurseve calls:

Call these functions in main() and calculate the following:

Example of executing a program:
% ./a.out
10! = 3628800
2^0 + 2^1 + 2^2 + ... + 2^9 + 2^10 = 2047
fibonacci 20: 6765
f(2) = 57.00

You may declare the coefficients an which are used by the Horner method as global array, since it is easy.

For example,
#define N 4
double a[N+1] = { 1, 2, 3, 4, 5 };

The array and the expansion correspond as it is shown on the figure:
the array and the expansion

Question 3

ex04-3-skel.c is a program which creates a PostScript file star.ps. A following image is drawn in the star.ps.
fractal
Edit this program and create a PostScript file in which the following image is drawn.
fractal

A function star() draws imege in this program. Edit this function. A function line() which used in star() draws lines. For example, line(1,2,3,4) draws line from position (1,2) to position (3,4).

If you finish this question, please try Koch curve.


Written by Naoki Wakamatsu.