基本原理：数学归纳法

1. 验证 P(1) 成立；
2. 证明如果 P(k) 成立，那么 P(k+1) 也成立；
3. 联合 1 和 2，证明由 P(1) → P(n) 成立。

<aside> 💡

证明：1 + 3 + … + ( 2n - 1 ) = n²

( n - 1 )² + ( 2n - 1 ) = n²

</aside>

递归函数设计的三个重要部分：

1. 给递归函数一个明确的语义；
2. 实现边界条件时的程序逻辑（P(1)）；
3. 假设递归函数调用返回结果是正确的，实现本层函数逻辑（P(k) → P(k+1)）。

【示例】递归求阶乘：

int f(int n) {
	if (n == 1) return 1;
	return f(n - 1) * n;
}

路飞吃桃

路飞买了一堆桃子不知道个数，第一天吃了一半的桃子，还不过瘾，又多吃了一个。以后他每天吃剩下的桃子的一半还多一个，到 n 天只剩下一个桃子了。路飞想知道一开始买了多少桃子。

输入

输入一个整数 n (2 ≤ n ≤ 30)。

输出

输出买的桃子的数量。