P4755 奇数求和（入门）

解题思路

这道题要求我们把 0 到 n 之间所有的奇数加起来，而且要求用递归来做。比如 n = 3，奇数是 1 和 3，1 + 3 = 4，所以答案是 4。

递归的思路是"大事化小"。我们可以定义一个函数 sumOdd(n)，它表示"1 到 n 之间所有奇数之和"。怎么把这个问题变小呢？分两种情况：

• 如果 n 是偶数，比如 n = 4，那么 4 本身不是奇数，不用加，答案和"1 到 3 的奇数和"一样，也就是 sumOdd(4) = sumOdd(3)；
• 如果 n 是奇数，比如 n = 5，那么 5 是奇数，一定要加上，然后再求"1 到 3 的奇数和"，也就是 sumOdd(5) = 5 + sumOdd(3)。

写成式子就是：n 是偶数时 sumOdd(n) = sumOdd(n-1)；n 是奇数时 sumOdd(n) = n + sumOdd(n-2)。

函数什么时候停下来呢？当 n 小于等于 0 时，已经没有奇数了，直接返回 0。这就是递归的"出口"，保证程序不会无限循环下去。

可以把这个递归想象成"倒着爬楼梯"：每次都把 n 减小一点，一直减到 0，再把一路上捡到的奇数一个个加起来。这个思路非常清晰，也不容易出错。奇数求和还有一个巧妙的规律：1 到 n 的所有奇数之和等于 (n+1)/2 的平方，不过题目要求我们用递归，所以我们就老老实实按递归来做。

参考代码

// 奇数求和：用递归求0到n之间所有奇数之和（含n本身）
#include <iostream>
using namespace std;

// 递归求1到n所有奇数之和
int sumOdd(int n) {
    if (n <= 0) return 0;                 // 没有奇数可加了
    if (n % 2 == 0) return sumOdd(n - 1); // n是偶数不加入，继续看n-1
    return n + sumOdd(n - 2);             // n是奇数就加上，再往前数2
}

int main() {
    int n;
    cin >> n;
    cout << sumOdd(n) << endl;
    return 0;
}

复杂度分析

每次调用递归，n 要么减少 1，要么减少 2，所以最多调用大约 n 次，时间复杂度是 O(n)。n 最大是 100，100 次运算瞬间完成。递归的深度也就是 n 层，空间占用 O(n)。这道题不用任何数组和循环，用"递归"这个工具，把求和这种本来用循环就能解决的问题换了一种漂亮的写法。