P4748 输出序列第n个数（入门）

解题思路

题目给了一个等差数列：1、3、5、7、9……相邻两个数相差 2。问第 n 个数是多少。

我们可以发现规律：第 1 个数是 1，第 2 个数是 3，第 3 个数是 5……每个数都比前一个数大 2。所以用递归：f(n) = f(n-1) + 2，当 n=1 时 f(1)=1，这就是递归的出口。

用例子验证：f(6)=f(5)+2=(f(4)+2)+2=…=1+2×5=11，和样例一致。其实这个序列第 n 个数就是 2n-1，但题目要求用递归完成，所以我们按递归的方式写。

递归的过程就像一个接力赛：要求 f(6)，先问 f(5) 是多少；f(5) 又问 f(4)……一直问到 f(1)=1，然后再一层一层加回来：f(2)=3，f(3)=5，f(4)=7，f(5)=9，f(6)=11。每一个数都要等前一个数算出来，才能算出自己。

边界情况：n=1 时直接返回 1，不递归。题目保证 1≤n≤100，递归最多 100 层，非常安全。f(100)=199，int 完全装得下。

参考代码

// 输出序列第n个数：等差数列1,3,5,...，第n个是前一个加2，用递归
#include <iostream>

int f(int n) {
    if (n == 1) return 1;        // 第1个数是1
    return f(n - 1) + 2;         // 每个数比前一个大2
}

int main() {
    int n;
    std::cin >> n;
    std::cout << f(n) << "\n";
    return 0;
}

复杂度分析

从 f(n) 一路递归到 f(1)，一共调用 n 次，每次只做一次加法和一次判断，所以时间复杂度是 O(n)。当 n=100 时只做 100 次运算，速度飞快。空间上递归深度是 n 层，占用 O(n) 的栈空间，n 最大 100，栈空间完全足够，不会溢出。整个思路就是"第 n 个数 = 第 n-1 个数 + 2"，简单清晰。