SICP 1.2

1.2 手続きとその生成するプロセス

1.2.1

再帰的プロセス(recursive process)と反復的プロセス(iterative process)

手続きの定義の中で自分自身を再帰的に呼び出していく。

SICPで勉強を始めた時(=ソフトウェアの仕事を始めたばかりの頃)、最も関心したのがこの部分。
インタプリタが保持すべき情報量のオーダーがO(1)なのかO(n)なのか。
反復プロセスの場合、常に一定の記憶量でループを処理する事が可能。

C,Pascal等では反復的プロセスを行いたくとも、再帰呼び出しの際に
スタックを次々消費していくよう設計されている。
反復プロセスにはfor,while等の特殊なループ構造が必要。

また、Schemeの実装は末尾再帰的(固定記憶領域で再帰呼び出しが可能な性質)である事が
IEEE企画で定められている。

1.2.2

木構造を意識した再帰の実装。
与えられた題意から再帰的プロセスを導くのは比較的簡単(直感的に落とし込みやすい)だが、
反復的プロセスの実現は難しく感じる。

1.2.3

計算量(O(n))の話

1.2.4

再帰・反復用のコードの実装練習

q-1.16
反復的アルゴリズム設計のためのヒント

• > 再帰時にその値が変化しない、不変量を定義すること

1.2.5 / 1.2.6

若干数学寄りの話なので略

まとめ

再帰的プロセス(recursive)と反復的プロセス(iterative)の違いが非常に重要。
自分自身を再帰的に呼び出す機能自体は同じだが、
インタプリタが計算終了までに記憶しておくべき記憶量に多大な差が生じる。

再帰回数が膨大になると(Cなどでは)スタックオーバーフローを起こす事になる。