C exercises(b) Recursive call

東京魅力PRサークル会員募集中

http://svn.mki.biz/pukiwiki/index.php?u-tokyo

興味があれば、ぜひコメントください。

階乗の計算

皆さんは「階乗の計算」を覚えていますか？ 5の階乗なら「5!」と表記し，

5! = 5 × 4 × 3 × 2 × 1

と計算します。つまり答えは120です。

0 の階乗：1
1 の階乗：1
2 の階乗：2 × 1
3 の階乗：3 × 2 × 1
– – – – – – –
n の階乗： n × (n – 1) × (n – 2) – – – 3 × 2 × 1
– – – – – – –

方法１）掛け算を続けることで階乗を求め

n! = n × (n-1) × (n-2) .. × 1

#include <stdio.h>

long Factorial1(int n) ;
long Factorial2(int n) ;
void main(void);

  /* 階乗を求める（非再帰版） */
long Factorial1(int n)
 {
    long p = 1L;

    if (n < 2)       /* nが０か１なら */
        return (1L); /* １を返す */
    else if (n > 1) {
        for ( ; n > 0; n--)
            p = p * n;
            return (p);
    }
}	


void main(void)
{
    int n;
    long f;

    printf("整数を入力して下さい\t");
    scanf("%d", &n);

    f = Factorial1(n);
    printf("Factorial1(  ) = %ld\n", f);

}

 

方法２）関数の中から自分自身を呼び出す

再帰呼び出し (recursive call）とは，関数の中から自分自身を呼び出すプログラミングのテクニックです。再帰呼び出しで階乗の計算式を考えてみると，

n! = n × (n-1)!

と定義できることがわかるでしょうか。

#include <stdio.h>

long Factorial1(int n) ;
long Factorial2(int n) ;
void main(void);

  /* 階乗を求める（再帰版） */
long Factorial2(int n)
 {
    if (n < 2)        /* nが０か１なら */
        return (1L);  /* １を返す */
    else              /* nに自分より１小さい自分を掛ける */
        return (n * Factorial2(n -1));
}

void main(void)
{
    int n;
    long f;

    printf("整数を入力して下さい\t");
    scanf("%d", &n);

    f = Factorial2(n);
    printf("Factorial2(  ) = %ld\n", f);
}

再帰呼び出しを使う上で、大切なポイントが２つあります。

 

１．終着点があること 呼び出しが無限に繰り返されてはなりません。再帰とは再び帰ってくるということ。そのためには終着点が必要になります。nの階乗はn=1が終着点です。

 

２．関数を抜けるときは元に戻す グローバルな変数を用いて状態を把握している場合、関数を抜けるときは関数に入ったときの状態に必ず戻すようにして下さい。そうしないと探索の整合性が失われてしまいます。

 再帰は使うべきか

一般に次のことが言えます。

• 再帰プログラムは計算機に負荷をかけるプログラムである。
• 時によっては，膨大な負荷をかけることもある。
• 簡単に非再帰プログラムとして書けるものは再帰プログラムを使うべきではない。

それでも，再帰プログラムが基本的であると言われるのは何故でしょうか。それは再帰プログラムが大きな力を秘めているからです。つまり

• 再帰プログラムでは簡単に書けるが，非再帰プログラムはかなり複雑なプログラムになってしまうようなものがある。

ということです。

このような問題が意外とあるのです。再帰プログラム技法を，身につけたら，プログラミングを行う際，次のような視点で考えるのが良いかもしれません。

• まずは，非再帰プログラムで問題を考えてみる。
• 難しいと判断した場合，再帰プログラムで考えてみる。

再帰が有効な例

• ハノイの塔
• データの木構造, 入れ子構造
• XML文書
• ファイルシステム

演習

再帰呼び出しの方法で、整数を二進数で表示するプログラムを作成

/*
実行例

12345678
101111000110000101001110

*/

ヒント

void print_binary(unsigned int n)
{
    if (n >= 2) print_binary(n/2);
    printf("%d", n%2);
}