阶乘的运算法则的运行 前n项阶乘的和公式
从熟悉的数学开始。1.线性迭代和递归线性递归和迭代先说“阶乘”。n! = n *(n-1)*(n-2)....3*2*1计算“阶乘”的方法有很多种，最直观的一种解法(从N开始递减)。n!=n?[(n?
从熟悉的数学开始。
1.线性迭代和递归线性递归和迭代先说“阶乘”。
n! = n *(n-1)*(n-2)....3*2*1
计算“阶乘”的方法有很多种，最直观的一种解法(从N开始递减)。
n!=n?[(n?1)?(n?2)?3?2?1]=n?(n?1)!
由函数直接表示为:
> function factorial(n) {... return n === 1... ? 1... : n * factorial(n-1);... }undefined> factorial(6)720
绘制函数执行的Shape：
绘制函数执行的形状:
一个计算6！。
接下来，我们换个角度来看。从1开始，乘以n:
product <-- counter * productcounter <-- counter + 1
当计数器超过n时，输出乘积结果。
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);# 最终的结果放在前面
同样可视化其执行过程如下：
另外，将它的执行过程可视化如下:
一个计算6的线性迭代过程！。
分析了第一种递归结构，执行结构先扩展后收缩动作。扩展过程基于多层延迟操作；当收缩过程发生在操作的实际执行中时，这种类型的延迟操作被称为递归过程。
相反，第二个函数没有增长和收缩过程。在每一步，n的记录，即产品、计数器和最大计数，都被跟踪。这个过程称为线性迭代过程。
两者的区别在于，在交互的情况下，所有的状态信息都保存在每个进程中；在递归情况下，编译器维护隐藏信息。
在尾递归机制下，迭代递归将作为迭代过程来执行。
2.树递归第二种“进化模式”是“树递归”，以斐波那契数列为例:
0,1,1,2,3,5,8,13,21,…
Fibonacci数列有如下定义：
斐波那契数列定义如下:
斐波那契数列
简单粗暴地实现定义:
function fib(n) { return n === 0 ? 0 : n === 1 ? 1 : fib(n - 1) + fib(n - 2);}fib(6);
此函数在时间线里演变呈现“树状结构”：
该功能演变成时间线中的“树形结构”:
在计算(fib 5) fib(5)中生成的树递归过程
但是，这种解决方案的运行效率极低。从图中可以看出，fib (1)，fib (2)，fib (3)是重复计算的。
值得一提的是Fib(n)的值无限接近n/√ 5。它的“黄金比例”在哪里:
?2=?+1
到目前为止，已知函数的“开发模式”是树形结构。接下来，如何判断这个功能动作是“坏棋”还是“好棋”？答案是从“时间复杂度”和“复杂度在空”两个方面。
所以我们可以看到fib(n)函数在“时间复杂度”上是指数增长的；另一方面，”空之间的复杂度是“线性递增”的。总之，树递归的总步骤数取决于节点总数；所需的空间隔与生成树的最大深度成正比。
相比之下，尝试用迭代法计算斐波那契。使用一对数字a和b，初始化Fib(1)=1和Fib(0)=0，并重复应用以下转换:
a <--- a + bb <--- a
a和b的值最终将分别对应于Fib(n+1)和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);}
第二种解决方案是“线性迭代”。
比较以上两种解决方案。树递归的解决方案更直观，有助于在初始阶段整理上下文；然而，第二个线性递归解决方案需要更多的观察，注意计算过程需要三个状态变量。
