先從熟稔的數學着手起步。

1.線型迭代與遞歸 Linear Recursion and Iteration

我們從「階乘」開始。

n! = n *(n-1)*(n-2)....3*2*1

計算「階乘」的方法有很多，最直覺的一種解法（從n逐次遞減）

n!=n⋅[(n−1)⋅(n−2)⋯3⋅2⋅1]=n⋅(n−1)!

直接用function表達為：

> function factorial(n) {
... return n === 1
...        ? 1
...        : n * factorial(n-1);
... }
undefined
> factorial(6)
720

繪製函數執行的Shape：

A linear recursive process for computing 6!.

接下來，我們從另外一個視角審視。從1開始，逐次乘到n：

product <-- counter * product
counter <-- counter + 1

當counter超過n時，輸出product結果。

function factorial(n) {
    return fact_iter(1, 1, n);
}
function fact_iter(product, counter, max_count) {
    return counter > max_count
           ? product
           : fact_iter(counter * product,
                       counter + 1,
                       max_count);
}

factorial(5);
# 最終的結果放在前面

同樣可視化其執行過程如下：

A linear iterative process for computing 6!.

分析第一種遞歸結構，執行結構先expansion再constraction。expansion過程建立在層層的deferre-operatioin之上；而constraction過程發生於運算的實際執行中，此種類型的 deferred operations稱之為遞歸a recursive process。

於此相反，第二個函數沒有grow和shrink的過程。在每一步中，都對n追蹤記錄，即product, counter, and max-count。該過程稱之為 a linear iterative process.

二者的區別在於，interactive-case，所有的state信息都保存在每一個過程中；而在recursive-case中，編譯器維護着hidden-information。

在tail-recursion機制之下，iterative-recursion將會執行為iteration-process。

2.樹狀遞歸

第二種「演變模式」是「樹狀遞歸」，以Fibonacci數列為例：

0,1,1,2,3,5,8,13,21,…

Fibonacci數列有如下定義：

Fibonacci數列

簡單粗暴的將定義實現出來：

function fib(n) {
    return n === 0
           ? 0
           : n === 1
             ? 1
             : fib(n - 1) + fib(n - 2);
}

fib(6);

此函數在時間線里演變呈現「樹狀結構」：

The tree-recursive process generated in computing (fib 5) fib(5)

然而該解決方案的運行效率極低，從圖中可知，fib(1), fib(2), fib(3)重複計算。

頗為值得一提的是，Fib(n)的值無限趨近於ϕn/√5。其中 ϕ為「黃金比例」：

ϕ2=ϕ+1

至此，已知函數的「發展演變模式」為樹狀結構。下一步，如何判斷此函數動作是一部「臭棋」還是一步「好棋」呢？答案是從「時間複雜度」和「空間複雜度」兩方面着手分析。

於是，我們看到 fib(n)函數在「時間複雜度」上，指數級增長；而另外一方面，”空間複雜度」則「線性增長」。一言以蔽之，樹狀遞歸執行的總步數，取決於總的節點數量；而所需的空間則與生成樹的最大深度成正比。

作為對比，嘗試用iterative的方法計算Fibonacci。須用到一對數a和b，並初始化Fib(1)=1 and Fib(0)=0，反覆應用以下轉換：

a <--- a + b
b <--- a

a與b的數值最終將分別對應Fib(n+1) and Fib(n)。

function fib(n) {
    return fib_iter(1, 0, n);
}
function fib_iter(a, b, count) {
    return count === 0
           ? b
           : fib_iter(a + b, a, count - 1);
}

更加符合直覺的表達方式是：

function fib(n) {
    return fib_iter(1, 0, n);
}
function fib_iter(next, current, count) {
    return count === 0
           ? current
           : fib_iter(next + current, next, count - 1);
}

這第二種解法就是「線型迭代」。

對比以上兩種解法。Tree-Recursion的解法更加符合直覺，有助於在初步階段，梳理清楚脈絡；而第二種Linear-Recursion的解法則需要較多的觀察，注意到計算過程需要三個狀態變量。