再帰(Recursion)

関数それ自身が、自分を呼び出す場合。

関数の定義の中に関数自身を使用するようなもの。

関数の記述にそれ自身への参照があらわれるもの。

要素がそれと同等の要素データを含んでいる。

「再帰を利用することにより、関数は簡潔に定義される」例がある。

ループ処理(for 文, while 文) は再帰的に呼び出す形に書き換えることができる。

関連) ハノイ(hanoi)の塔, クイックソート, DNSの再帰的問い合わせ？, フラクタル図形 ・・・

再帰を使う上での、２つのルールを考慮するように！

無限の呼び出しは駄目。呼び出しの終わりを持つこと。

無理に使用しない。プログラムが簡単になる場合のみ使用する。

5 ! = 5 * 4 * 3 * 2 * 1 = 120

漸化式というものを学習した(高校の数学？)・・・C言語風に ( ) を使って表現すると・・・

kaijo( 0 ) = 1
kaijo( n ) = n * kaijo( n - 1 )

これをC言語のコードに書き換えると

int kaijo ( int n )
{
    if (n == 0)
        return ( 1) ;
    else
        return ( n * factor ( n - 1 ) ) ;
}

「漸化式の形式に書き表せるもの」　= 「再帰プログラミングに適している」
と言って良いだろう

 

/*      学籍番号 　氏名     日付      例題6-6: 階乗を求めるプログラム  */ #include <stdio.h> float kaijo(int n); int main( ) {     int i;     for (i = 0; i < 10; i++) {         printf("%d! = %f\n", i, kaijo(i));     } } float kaijo(int n) {     if (n > 1) {         return (n * kaijo(n - 1));     } else {         return ((float) 1);     } }

*) でも正直に言うと、階乗程度のプログラムに再帰は必要無い。再帰無しでも十分効率的なプログラミングが可能である。

 

#include <stdio.h> float kaijo(int n); int main( ) {     int i;     for (i = 0; i < 10; i++) {         printf("%d! = %f\n", i, kaijo(i));     } } float kaijo(int n) {     int i;     int k = 1;     for (i = 1; i <= n; i++) {         k = k * i;     }     return (k); }

練習) 同様にフィボナッチ(Fibonacci)数列をプログラムで計算し表現してみましょう。