递归求解等比数列求和

思路

递归

关于递归

提取公因式，获得递推方程，分类讨论k的奇偶性
$\begin{split}
\small(p^{0} {\small+} p^{1} {\small+} \dots {\small+} p^{k})=sum(p,k/2)\cdot(1 + p^{k/2+ 1})
\end{split}$

$$sum(p,k)=\begin{cases} sum(p,k/2)\cdot (1 + p^{k/2 \small+ 1}), \quad &k为奇数 \\ \\ sum(p,k-1)\cdot q \small+ 1, &k为偶数 \end{cases}$$

递推型

1. 前后关系：sum(n)与sum(n / 2)
2. 子问题状态：k
3. 递归结果：有返回值，局部变量
4. 递归出口：k == 0

代码

#include <iostream>
#include <cmath>
using namespace std;

int sum(int p, int k)
{
    if (k == 0) return 1;
    if (k & 1) return sum(p, k / 2) * (1 + pow(p, k / 2 + 1));
    else return sum(p, k - 1) * p + 1;
}

int main()
{
    int p, k;
    cin >> p >> k;
    cout << sum(p, k) << endl;
}