recursion - すべての再帰関数を反復関数として書き直すことはできますか?

Question

長い間この疑問を抱いていたのですが、答えがわかりません。問題は、すべての再帰関数に同じことを行う反復関数があるかどうかです。

例えば、

factorial(n) {
    if (n==1) { return 1 }
    else      { return factorial(n-1) }
}

これは繰り返し簡単に書き直すことができます:

factorial(n) {
    result = 1;
    for (i=1; i<=n; i++) {
        result *= i
    }
    return result
}

しかし、他にももっと複雑な再帰関数がたくさんあるので、一般的な答えはわかりません。これは、理論的なコンピューター サイエンスの問題でもある可能性があります。

Answer 1

理論に立ち向かわなくても、プロセッサー (Pentium など) が反復的に実行されることを観察することで、任意の再帰関数が同等の反復関数を持つことができることを自分自身に納得させるのは簡単です。