iphone - iPhoneで再帰を避けるべきですか?

Question

iPhone で実行されるコードで再帰を避けるべきですか?

または別の言い方をすれば、iPhoneの最大スタックサイズを知っている人はいますか?

Answer 1

はい、再帰を避けることは、すべての組み込みプラットフォームで良いことです。

スタック オーバーフローの可能性を低減または排除するだけでなく、多くの場合、より高速なコードも提供します。

再帰アルゴリズムはいつでも反復的に書き直すことができます。ただし、これは必ずしも実用的ではありません (クイックソートを考えてください)。これを回避する方法は、再帰の深さが制限されるようにアルゴリズムを書き直すことです。

イントロソートは、実際にどのように行われるかを示す完璧な例です。クイックソートの再帰の深さを log2 (要素数) に制限します。したがって、32 ビット マシンでは、32 より深く再帰することはありません。

http://en.wikipedia.org/wiki/Introsort

私は過去に組み込みプラットフォーム (カー エンターテイメント システム、電話、ゲーム コンソールなど) 向けのソフトウェアをかなり書いてきました。場所。

その結果、スタック オーバーフローで停止したプログラムはなく、ほとんどのプログラムは 32kb のスタックに満足しています。各スレッドが独自のスタックを取得するため、複数のスレッドが必要になると、これは大きな効果をもたらします。そのようにして、メガバイトのメモリを節約できます。

Answer 2

「再帰を使用しない」という答えがいくつかあります。私は同意しません-iPhoneが厳しく制限された組み込みシステムであるというわけではありません。問題が本質的に再発する場合は、そのように表現してください。

スタックの深さが数百または数千フレームになるまで繰り返し実行しない限り、問題が発生することはありません。

Answer 3

iPhoneの最大スタックサイズは?

iPhone は、ほとんどのオペレーティング システムと同様に、すべてのプロセスに有効なメモリ スペースが与えられる修正された OSX を実行します。

これは完全なプロセッサであるため、スタックが大きくなり、ヒープが小さくなります (視点によってはその逆も同様です)。これは、プログラムに割り当てられたメモリがなくなるまで、スタックがオーバーフローしないことを意味します。

スタックとパフォーマンス上の理由から (関数呼び出しは単純なループに比べてコストがかかる) できる限り再帰を避けるのが最善ですが、いずれにせよ、再帰関数に設定できる制限を決定し、長くなりすぎた場合はそれらを切り詰める必要があります。