tailRecursion.c

// 末尾再帰についての説明

/*********************************************************/
/* 処理概要:   nの階乗を返す (Int -> Int)                    */
/* 目的:      普通の再帰で書いたものと、末尾再帰で書いたものの比較  */
/*********************************************************/

// =====普通の再帰=====
int fact(int n)
{ 
    if (n <= 0) 
        return 1; 
    else 
        return n * fact(n-1); 
} 

// =====末尾再帰======
int fact( int n )
{ 
    return _fact( n, 1 ); 
} 
int _fact( int n, int a )
{
    if (n <= 0) {
        return a;
    } else {
        a *= n;
        return _fact( n-1, a );
    }
}

/*********************************************************/
/* 処理概要:   フィボナッチ数列の総和を求める(末尾再帰)           */
/*********************************************************/
int fib(int n, int a = 0, int b = 1)
 { 
    if(n <= 0) {
        return b - 1; 
    } else {
        return fib(n - 1, b, a + b); 
    }
}


// n番目のフィボナッチ数を返す関数 
int sub_fib (int n, int a = 0, int b = 1)
{ 
    if(n <= 1) {
        return a; 
    }
    return sub_fib(n - 1, b, a + b); 
}

増やされた引数は「蓄積変数」(accumulator)と呼ばれる。

アキュムレータは「途中経過が計算できるならその時点の途中経過を先に計算して終わらせてしまう」もの。
（逆にそうじゃないものはアキュムレータが非常に不格好になる）