C再帰と末尾再帰
2989 ワード
再帰(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; }