前n项阶乘的和公式 阶乘的运算法则的运行

先从熟稔的数学着手起步。

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的解法则需要较多的观察，注意到计算过程需要三个状态变量。