網絡学習管理 速習C言語入門3 C exercises(b) Recursive call

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
– – – – – – –

方法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が0か1なら */
        return (1L); /* 1を返す */
    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);

}

 

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

再帰呼び出し (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が0か1なら */
        return (1L);  /* 1を返す */
    else              /* nに自分より1小さい自分を掛ける */
        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);
}

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

 

 1.終着点があること

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

 

 2.関数を抜けるときは元に戻す

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

 再帰は使うべきか

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

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

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

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

ということです。

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

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

再帰が有効な例

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

演習

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

/*
実行例

12345678
101111000110000101001110

*/

ヒント

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

 

1 thought on “C exercises(b) Recursive call”

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA


Related Post

C exercises (2) stdioC exercises (2) stdio

標準ライブラリ関数 : 標準入出力関数 標準入出力関数には(C言語プログラミング)で説明した printf() や scanf() の他にも 下のように 1文字専用の入出力関数と 1行専用の入出力関数が用意されている。 標準入力から文字入力 getchar 関数 標準出力から文字出力 putchar 関数 標準入力から文字列入力 gets 関数 […]

C exercises(c) Command line arg.C exercises(c) Command line arg.

今まで、main 関数へ引数なしを意味する int main(void) と記述、 実は main関数にも引数を渡すことができます。 この main関数に渡す引数のことを「コマンドライン引数」といいます。 コマンドライン引数 main関数へ渡せる引数は、 引数の総個数 引数の文字列を指すポインタの配列 の 2つです。 一般に int main(int argc, char […]

C exercises(5) AddressC exercises(5) Address

ポインタの仕組み:アドレスとは ポインタはC言語(および拡張言語)に特有の概念で、C言語を学び始めた初心者が必ずといっていいほどつまづく概念でもあります。ポインタがどうしても理解できないためにC言語に挫折してしまう方もいます。 アドレスの基本 コンピュータの記憶装置(メモリ)には、アドレスが付けられている。 変数のアドレス 変数のアドレスを取得するには変数名の前にアンパサンド “&”をつけます。 int a = 123; printf(“aのアドレス : %p\n”, &a); 配列のアドレス 配列の先頭をアドレスは、配列名だけで示します。要素のアドレスは&配列名[添字]で示します。 #include <stdio.h> int […]