【C/C++】簡単な再帰関数の動作について考えてみる

関数の宣言方法

まず基本となる関数の宣言方法から。関数を使うためにはプロトタイプ宣言をしなければいけません。

#include  <stdio.h>

int Rec( int n ); // プロトタイプ宣言

int main ( void ) {
    
    // 処理  
    return 0;
}

プロトタイプ宣言はたくさんの関数が出てきた時に管理がしやすいです（たぶん）宣言した関数の内容は、その後であればどこでも書くことができます。

#include  <stdio.h>

int func( int n );   // プロトタイプ宣言

int main ( void ) {
    
    // 処理
    
    int ans = func( 5 ); // 25
    
    return 0;
}

int func( int n ) {

    return n * n;
}

また、宣言と同時に書くこともできます。

#include  <stdio.h>

int func( int n ) { // プロトタイプ宣言

    return n * n;
}

int main ( void ) {
    
    // 処理
    
    int ans = func( 5 ); // 25
    
    return 0;
}

再帰関数

再帰関数とは簡単に言うと再帰呼び出しをする関数のことです。 ＊再帰呼び出しとは自分で自分を呼び出すことです＊ 再帰的な構造をもつアルゴリズム（再帰的アルゴリズム）を記述する際に再帰関数を用いると簡単に書くことができます（当たり前）

階乗

階乗とはその数から1までを掛け合わせていく計算です。

\begin{align} n! &= \prod_{k=1}^n k \\ \\ & = n * ( n - 1 ) * ( n - 2 ) * … * 3 * 2 * 1 \\ \end{align}

こんな式で表すことができます。1からnまでの総乗ですね

以下に示すプログラムは「n!」を計算しています。

#include <stdio.h>

int Rec( int n ) {

    // 何かしらの処理
    
    // 0! = 1なので
    if ( n == 0 ) {
    
        return 1;
    }else {
    
        return n * Rec( n - 1 );
    }
}

int main ( void ) {
        // 省略
        int ans = Rec( 4 );
        printf( "%2d\n", ans ); // 24
}

この場合関数の呼び出され方としては

Rec( 4 ) : 4 * Rec( 3 );
Rec( 3 ) : 3 * Rec( 2 );
Rec( 2 ) : 2 * Rec( 1 );
Rec( 1 ) : 1 * Rec( 0 );
Rec( 0 ) : 1;

となり、これをそれぞれに代入していくと

Rec( 4 ) : 4 * 3 * 2 * 1 * 1 = 24

つまり「4!（4の階乗）」ということになります

フィボナッチ数列

次にフィボナッチ数列を計算してみましょうフィボナッチ数列とは１つ前の項と２つ前の項を足していく数列です

\begin{align} F_0 &= 0\\ F_1 &= 1\\ F_n &= F_{n-1}\; + F_{n-2} \end{align}

しかし、これでは $F_{50}$ 項目を求めようとしたら $F_0$ 〜 $F_{50}$ 項まで求めないといけません。以下に $F_n$ 項目を求める一般式を書きます

$\begin{align} F_n &= \frac{1}{\sqrt{5}}\left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} \\ \\ &= {{\phi^n - (1-\phi)^n} \over \sqrt{5}} \\ \\ &= {{\phi^n - (-\phi)^{-n}} \over \sqrt{5}} \\ \\ \phi &\equiv \frac{1+\sqrt{5}}{2} \simeq 1.618033988749895 \end{align}$

プログラムを組むには前者の方が向いてますよね（処理速度は気にしない...）以下がフィボナッチ数列を求めるコードになります

#include <stdio.h>

int fibonacci( int n ) {
    switch ( n ) {
        case 0: return 0;
        case 1: return 1;
        default: return fibonacci( n - 2 ) + fibonacci( n - 1 );
    }
}

void main(void) {
    int n;
    printf( "n = " );
    scanf( "%d", &n );
    printf( "F(%d) = %d\n", n, fibonacci( n ) );
}

この関数の呼び出しを追うのは少し難しいと思いますが、考えがわかれば簡単です。 $F_6$ を求めるとフィボナッチ数列 0 1 1 2 3 5 8 13 21 ... から $F_6 = 8$ ですね上のプログラムの動作としては n = 6 なので

fibonacci( 6 ) : fibonacci( 4 ) + fibonacci( 5 )
fibonacci( 5 ) : fibonacci( 3 ) + fibonacci( 4 )
fibonacci( 4 ) : fibonacci( 2 ) + fibonacci( 3 )
fibonacci( 3 ) : fibonacci( 1 ) + fibonacci( 2 )
fibonacci( 2 ) : fibonacci( 0 ) + fibonacci( 1 )
fibonacci( 1 ) : 1
fibonacci( 0 ) : 0

それぞれ代入していくと

fibonacci( 6 ) : fibonacci( 4 ) + fibonacci( 5 ) // 8
fibonacci( 5 ) : fibonacci( 3 ) + fibonacci( 4 ) // 5
fibonacci( 4 ) : fibonacci( 2 ) + fibonacci( 3 ) // 3
fibonacci( 3 ) : fibonacci( 1 ) + fibonacci( 2 ) // 2
fibonacci( 2 ) : fibonacci( 0 ) + fibonacci( 1 ) // 1

となり $F_6 = 8$ を求めることができました。めでたしめでたし

f:id:nomunomu0504:20190411151221p:plain:w0