初见递归｜递归函数求猴子吃桃——常规吃桃问题的一种变形

题目

题面描述

猴子在第一天摘了若干个桃子（奇数），吃掉了桃子的一半多一个，第二天吃掉了剩下桃子的一半多一个，以后每天都吃掉剩下桃子的一半多一个，直到第n天，桃子只剩1个，不再吃桃。

编写递归函数，猴子用day天吃到桃子只剩1个，则最开始有多少个桃子，如调用tao(3) 得到的返回值是7（第1天有7个桃子，第2天有3个桃子（猴子吃掉了7/2+1）,第3天剩余有1个桃子）。

函数接口定义：

int tao(int day);

i 是用户传入的参数,是int值，表示第i天； 函数调用结束后得到第i天剩余的桃子数量。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：

#include<iostream>
using namespace std;
int tao(int day);
int main()
{
 int day;
 cin >> day;
 int n = tao(day);
 cout << n;
 return 0;
}
/* 请在这里填写答案 */

输入样例1:

3

输出样例1:

7

输入样例2:

4

输出样例2:

15

输入样例3:

5

输出样例3:

31

作者: 陈春丽
单位: 中国地质大学（北京）
时间限制: 400 ms
内存限制: 64 MB

递归问题的一般思考方向

运用递归需要明确三个要素：

1. 函数用途
2. 终止条件
3. 递推关系

记住这三点，递归问题就容易解决了。

问题分析

常见经典猴子吃桃递归问题为：已知吃到第十天桃子余 $1$，求最初有多少桃。

此问题有所不同，函数输入的形参为吃到第 n 天桃子余 1 的 n，比经典版本更加灵活，难度稍有增加，但问题本质不变。

数学化抽象

设第 n 天有 f (n) 个桃子，则第 n-1 天有 f(n-1) 个桃子

由题意可知，第 n 天有一个桃子，第 n-1 天有 1×2+1=3 个桃子……

则有 f (n) = 2 × f (n - 1) + 1

当 n-1=1 时，递推结束

代码实现

int tao(int day) {
    //终止条件
    if (day == 1) {
        return 1;
    } else {
        //递推关系
        return (tao(day - 1) * 2 + 1);
    }
}