程序员的数学 - 递归 - 自己定义自己 - 阅读小结

递归

当碰到一个难题，我们需要联系到汉诺塔，进行如下思考：

“能够将复杂问题转换为较为简单的同类问题么?”

这就是递归的思维。

根据递归结构建立递归公式，并最好总结出递归解析式。

汉诺塔

递归公式：

H(n)={0,H(n−1)+1+H(n−1), n = 0n = 1, 2,3,4.... $$H(n)=\{\begin{array}{ll}0,& \text{ n = 0}\\ H(n-1)+1+H(n-1),& \text{n = 1, 2,3,4....}\end{array}$$

阶乘

递归公式：

n!={1,n∗(n−1)!, n = 0n = 1, 2,3,4.... $$n!=\{\begin{array}{ll}1,& \text{ n = 0}\\ n\ast (n-1)!,& \text{n = 1, 2,3,4....}\end{array}$$

斐波那契数列

递归公式：

f(n)=⎧⎩⎨0,1,f(n−1)+f(n−2), n = 0n = 1n = 2,3,4,5.. $$f(n)=\{\begin{array}{ll}0,& \text{ n = 0}\\ 1,& \text{n = 1}\\ f(n-1)+f(n-2),& \text{n = 2,3,4,5..}\end{array}$$

杨辉三角形 与 组合总数

找出问题中的递归

1. 从整体问题中隐去部分问题，
2. 判断剩余部分是否和整体问题时同类问题

=>

1. 从n层的整体问题中隐去部分问题。
2. 判断剩余部分是否是n-1层的问题。