几个经典的递归问题

前言

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

阶乘问题

阶乘的定义很简单

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) = 0F(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)=1F(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代码实现

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180904G0038P00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励