Chapter 1.2
Exercises 1.2
Note
- A procedure is a pattern for the local evolution of a computational process. It specifies how each stage of the process is built upon the previous stage. We would like to be able to make statements about the overall, or global, behavior of a process whose local evolution has been specified by a procedure. This is very difficult to do in general, but we can at least try to describe some typical patterns of process evolution.
- 手続きとは, 計算プロセスの部分的な発展のパターンのこと.
- この節では, シンプルな手続きが生成する共通したプロセスの発展パターンを見る
- (define (fact-recur n) (if (= n 1) 1 (* n (fact-recur (- n 1)))))
- A linear recursive process: 処理系がどこまで処理が進んだかを保存しておかないと評価できない.
- (define (fact-iter prd cnt n) (if (> cnt n) prd (fact-iter (* cnt prd) (+ cnt 1) n)))
- A linear iterative process: 手続きの状態は状態変数(state variables)で完全に決まるので, 状態変数を与えれば評価できる
- In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure
- 再帰(recursion)と反復(iteration)を対比する場合, プロセスと手続きを混同しないように気をつけなければならない. 手続きが再帰的とは文法的に再帰的だということ. プロセスが再帰的というときはプロセスの発展パターンに言及している.
- 反復的手続きは, loop構造で記述できる
- Tree Recursive process: 計算プロセスがTreeのように発展. 計算ステップはTreeの葉の数に比例, 計算領域はTreeの最大深さに比例.
- ステップ数は指数関数的に増加. 階層構造の処理, プログラムの設計, 理解がしやすい.
