algorithm - 再帰で解決できるすべての問題はループで解決できますか？

Question

再帰で解決できるすべての問題はループで解決でき、その逆も同様です。

この声明は正しいですか、それとも証明されていますか？再帰を使用すると、スタックオーバーフローが発生する場合があります。ステートメントが正しい場合。代わりにループを使用することをお勧めします。

ありがとう

Answer 1

はい。Loop + Stackは、すべての再帰の問題を解決します。

結局のところ、コンパイラはそれを内部的に行います。再帰は、データをスタックにプッシュし、後でコンパイラーによってスタックからポップすることに他なりません。

Answer 2

通常、対応する反復（ループ）ソリューションには同じ量のストレージが必要ですが、明示的に管理する必要があります。