algorithm - 再帰的および反復的な実行時間

Question

再帰的戦略と反復的戦略の両方で同じ実行時間がかかるアルゴリズムがいくつかあることは知っています。しかし、私はそのベースを決定することはできません。

再帰的戦略と反復的戦略の両方を備えたアルゴリズムの実行時間が常に同じになる可能性はありますか?

Answer 1

すべての再帰アルゴリズムは、(同じ実行時間で) 反復アルゴリズムに減らすことができます。 http://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration

Answer 2

はい、末尾再帰を使用するようにアルゴリズムを最適化できる場合、追加のコードなしで反復に変換できるため、実行時間は同じになります。

Answer 3

同じ時間の複雑さになる可能性がありますが、一定のオーバーヘッドはおそらく異なります (再帰はおそらくより高価になります)。さらに、再帰は、反復アプローチが使用されている場合には存在しない余分なスペースの複雑さを追加します。