C再帰と末尾再帰

再帰(Recursion)
スタック

先進後出(FILO,First In Last Out)

は、関数呼び出し(Call)および戻り(Return)の順序

を満たす.

は、各関数呼び出し情報を戻してから解放するまで維持する必要があり、メモリ容量は

である.
さいきかんすう

ベースライン条件(Base Condition)

再帰条件(Recursive Condition)

// factorial.c
#include 

int fact(int n) 
{
    if (n < 0) return 0; else if (n == 1 || n == 0) return 1; else return n-- * fact(n); } int main(void) { for (int i = -1; i <= 10; i++) printf("%d! = %d
", i, fact(i)); return 0; } 

テール再帰

再帰的にメモリを消費する問題を解決する

関数のすべての再帰形式の呼び出しは、関数の末尾

に現れる.

再帰呼び出しが関数体全体で最後に実行する文であり、その戻り値が式の一部ではない場合、この再帰呼び出しが最後の再帰

である.

回帰プロセスは何もしない

コンパイラが関数呼び出しが末尾再帰であることを検出すると、スタックに新しい

を作成するのではなく、現在のアクティブなレコードが上書きされます.

// factorial.c
#include 

/* a    1 */
int fact(int n, int a) { if (n < 0) return 0; else if (n == 0) return 1; else if (n == 1) return a; else return fact(n - 1, n * a); } int main(void) { for (int i = -1; i <= 10; i++) printf("%d! = %d
", i, fact(i, 1)); return 0; }