【递归】递归公式

原创 老姚 随笔 递归,俺跟你拼了 789阅读 2017-05-09 16:22:37 举报

高中时,我们都学过数列,也学过递归公式。
如果你能写出问题的递归公式,那么转化为代码,就是非常轻松的事情。

1.求n的阶乘
递归公式:
[quote]f(n) = n * f(n-1)
f(1) = 1[/quote]
转化为代码:
javascript 代码

2.斐波那契数列
递归公式:
[quote]f(n) = f(n-1) + f(n-2)
f(0)= f(1) = 1[/quote]
转化为代码:
javascript 代码

3.等差数列
递归公式:
[quote]f(n) = f(n-1) + 3
f(1) = 1[/quote]
转化为代码:
javascript 代码

4.等比数列
递归公式:
[quote]f(n) = 2 * f(n-1)
f(1) = 1;[/quote]
转化为代码:
javascript 代码

5.爬楼梯问题
最后来一个不那么明显的问题,爬楼梯问题。
说一个楼梯有n节台阶,
你可以一步迈上1个台阶,
也可以一步迈上2个台阶,
不怕扯到蛋,甚至可以一步3个台阶,
请问楼梯爬法的所有可能。

问题看起来很难的,我们假设有10个台阶,以便于我们分析。
f(10)表示所有的可能。
假如你第一步,只跨了1个台阶,还剩下9个台阶没走,那么所有可能就是f(9),
假如你第一步,跨了2个台阶,那么所有可能就是f(8),
假如你第一步,跨了3个台阶,那么所有可能就是f(7)
因此我们便得到递归公式:

f(n) = f(n-1) + f(n-2) + f(n-3)
我们还得确定边界条件:
[quote]f(1)=1
f(2)=2
f(3)=4[/quote]
其中f(3)的4种可能是这样的:
[quote]1 1 1
1 2
2 1
3[/quote]
直接转化为代码:
javascript 代码

其实不管多么复杂的问题,只要有了递归公式,翻译成代码就是easy的。
但能用递归公式表达的问题都是比较偏向于数学问题,在计算机程序中,适用面必然有限。

本文完。

《递归系列目录》

看到此处,我们该想到,陆游诗人对前端界做出的最大贡献:
纸上得来终觉浅,绝知此事要躬行。

评论 ( 3 )
最新评论
ai782041 2018-01-18 11:22:19 3F

厉害了

babaxiaomoxian 2017-05-21 10:18:33 2F

aaawhz 2017-05-15 19:06:23 1F

算法研究多了, 可以去做人工智能.. 前端可视化工具. 未来有前景