space-complexity - 再帰的アルゴリズムのスペースの複雑さ

Question

私はインタビューで、pallindromeのチェックの問題を解決するための効率的な方法を尋ねられました。

今、私は2つのことを行うことができます：

1. i=0からi=n / 2まで開始し、i番目とn番目の文字を比較して等しくなります。
2. 再帰を使用して、最初と最後が同じで、文字列の残りの部分がpallindromeであるかどうかを確認できます。

2番目は再帰的です。私の質問は、アルゴリズムの再帰バージョンと非再帰バージョンのスペースの複雑さの違いは何ですか？

Answer 1

で読んでください

1. http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
2. 再帰または反復？

基本的に、再帰呼び出しは実行スタックに格納されるため、再帰アルゴリズムはオーバーヘッドを追加します。

ただし、再帰関数が呼び出しの最後の行（末尾再帰）である場合、追加のペナルティはありません。

もちろん、両方のアルゴリズムは同じです。

Answer 2

理論的には、それらは同じ空間の複雑さを持っています。これは、末尾再帰を最適化できるかどうかに大きく依存します。

その場合、スタックは再帰ごとに置き換えられるため、ペナルティは発生しません。