几个经典的递归问题

前言

上一篇中，使用递归算法优雅地解决了汉诺塔问题。实际上，凡是问题中存在递归结构的问题，都能使用递归算法来解决。下面就来解决几个经典的递归问题。

阶乘问题

阶乘的定义很简单

n! = n * (n-1) * (n-2) * … * 2 * 1 (n=1, 2, 3, 4, …)

0! = 1

需要特别注意，这个特殊情况。因为阶乘（一般的阶乘，这里不考虑其他阶乘情况）是定义域是正整数，所以如果没有这个情况，那么，这样就无法实现正确的递归定义。所以，需要额外的定义。

列举几个阶乘的表达式

0! = 1

1! = 1 * 1 = 1 * 0!

2! = 2 * 1 = 2 * 1!

3! = 3 * 2 * 1 = 3 * 2!

很明显，对于阶乘定义函数中定义域内任何一个整数而言，其乘式结构都是递归的。

递归结构式子为：n! = n * (n-1)!

递归终止的情况就是0! = 1

Python代码实现

斐波那契数列

斐波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出

这里需要注意的是，。

因此，斐波那契数列的递归表达式为

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2) (n = 2, 3, 4, …)

从递归表达式中找出两个关键信息

递归终止情况：F(0) = 0和F(1) = 1

递归通项式：F(n) = F(n-1) + F(n-2)

Python代码实现

斐波那契数列类型问题

求2/1 + 3/2 + 5/3 + … 前20项之和

仔细观察这个式子会发现，分子分母出现是有规律的，其规律符合的就是斐波那契数列。

规律一：分母分子依次交替出现：1, 2, 3, 5, 8, 13, …；该斐波那契数列第一项为1，第二项为2

规律二：组成前3项分数，需要斐波那契数列前4个数；因此组成前20项，需要斐波那契数列前21个数

由上面表达式可知

递归通项式：F(n) = F(n+1) / F(n)

递归终止情况：F(1)=1和F(2)=2

Python代码实现

猴子吃桃问题

有一只猴子摘了一大堆桃子吃，它按照这样的规律吃桃子：第一天吃一半多一个，第二天吃第一天剩余的一半多一个，第三天吃第二天剩余的一半多一个…以此类推，当第七天时，恰好只剩下一个桃子。求猴子一共摘了多少个桃子？

这道题目的递归结构其实是有点奇怪的，奇怪之处就在于，它的递归结构是的。

因为题目给定的条件就是：第七天，只剩下一个；又根据规律，可以写出下面的一系列表达式

n：表示第几天 F(n)：表示第n天有多少个桃子

F(7) = 1

F(6) = ( F(7) + 1 ) * 2

F(5) = ( F(6) + 1 ) * 2

F(4) = ( F(5) + 1 ) * 2

…

F(n) = ( F(n+1) + 1 ) * 2

通过上面一系列的表达式，可以发现递归结构的两个关键信息

递归通项式：F(n)=(F(n+1) + 1) * 2

递归终止情况：F(7) = 1

Python代码实现