アルゴリズムとデータ構造
演習第 4 回
再帰

問題１ ［印刷用 PostScript］

(1) 次のような数列がある。これらの数列の漸化式を書きなさい。

• 階乗 f(n) = n! の漸化式
• 初項 1、等比 2 の等比級数 f(n) = 20 + 21 + 22 + ... + 2n の漸化式
• フィボナッチ数列 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 第 n 項 f(n) の漸化式
• n 次多項式 f(x,n) = a0 xn + a1 xn-1 + ... an-1 x + an のホーナー法を使っての漸化式

(2) 以下のような関数 rule() がある（教科書とは若干異なる）。 関数 mark() は定規に線を引く関数であり、 例えば mark( 13, 3 ) は 13 の位置に高さ 3 の線を引く。 ここで、rule( 4, 12, 3); を実行した場合、 定規にはどのように線が引かれていくかを、順番に図示しなさい。

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);
  }
}

問題２

次の計算を行なう関数を再帰で書きなさい。

• 階乗
• 等比級数
• フィボナッチ数列の第 n 項の値
• 4 次多項式 f(x) = 1x4 + 2x3 + 3x2 + 4x + 5
  （ホーナー法を用いる）

また、main() 関数でそれらの関数を呼び出し、 以下の値を計算させて表示させなさい。

• 10!
• 初項 1、等比 2 の等比数列の第 10 項までの等比級数
• フィボナッチ数列の第 20 項目
• x = 2 のときの 4 次多項式 f(x) = 1x4 + 2x3 + 3x2 + 4x + 5
  

実行例：
% ./a.out
10! = 3628800
2^0 + 2^1 + 2^2 + ... + 2^9 = 1023
fibonacci 20: 6765
f(2) = 57.00

int tousa(int n){
  if( n==0 ){
    return 0;
  }else{
    return n + tousa(n-1);
  }
}

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

問題３

ex04-3-skel.c は、実行すると star.ps という PostScript ファイルを生成する。 これを表示すると次のような画像になっている。

このプログラムを変更して、 このような画像 にしなさい。