网站后台无上传图片按钮优化推广网站推荐

本节通过学习解决一个有趣的问题来加深对递归的理解.

问题描述:

有一个猴子摘了桃子吃,第一天吃一半多一个,第二天吃第一天剩余的一半多一个,第三天吃第二天剩余的一半多一个..以此类推,当第n天时,恰好只剩下一个桃子.求猴子一共摘了多少桃子.

思路解析:

解读题目,第n天的桃子数量与第n-1天的数量关系如下:peach(n-1)=[peach(n)+1]*2

因此,想知道第一天的桃子数量必然需要知道第二天的桃子数量,就必然要知道第三天的桃子数量,以此类推,第n天的桃子数量就为1,递推关系十分清晰.那么接下来确定递归终止条件,当n等于1时,相当于达到了第n天的情况,即只剩下一个桃子,返回1给上层主调函数.

代码如下:

class Solution(object):def monkey(self, n):# 基本情况：如果只剩下1个桃子，则返回1if n == 1:return 1else:# 递归情况：计算前一天的桃子数量，然后加1（因为猴子多吃了一个），再乘以2（因为猴子吃掉了剩下桃子的一半）return (self.monkey(n-1) + 1) * 2