猴子吃桃.
本节通过学习解决一个有趣的问题来加深对递归的理解.
问题描述:
有一个猴子摘了桃子吃,第一天吃一半多一个,第二天吃第一天剩余的一半多一个,第三天吃第二天剩余的一半多一个..以此类推,当第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个桃子，则返回1
if n == 1:
return 1
else:
# 递归情况：计算前一天的桃子数量，然后加1（因为猴子多吃了一个），再乘以2（因为猴子吃掉了剩下桃子的一半）
return (self.monkey(n-1) + 1) * 2