如何用递归生成Sn序列？需基于string函数与stoi实现

问题描述 #

序列Sn的定义规则：

• S₁是仅含数字1的序列，对应字符串 "1"
• 当n≥2时，Sₙ由Sₙ₋₁、字符串形式的n、Sₙ₋₁按顺序拼接而成，元素间用逗号分隔。例如S₂为1,2,1，S₃为1,2,1,3,1,2,1

递归实现代码（C++） #

#include <string>

std::string generateSn(int n) {
    // 递归终止条件：n=1时直接返回基础序列
    if (n == 1) {
        return "1";
    }
    // 递归获取前一个序列的字符串结果
    std::string prev_seq = generateSn(n - 1);
    // 按规则拼接当前序列
    return prev_seq + "," + std::to_string(n) + "," + prev_seq;
}

关键说明 #

• 基线逻辑：n=1是递归的终止点，直接返回最基础的序列字符串，避免无限递归
• 递归拼接：完全遵循题目定义的序列生成规则，通过递归拆解问题，先得到Sₙ₋₁再完成拼接
• 类型转换：使用std::to_string()将整数n转为字符串，适配拼接需求（题目提到的stoi是字符串转整数，此处用反向转换更合理）

测试验证 #

• 输入n=2，返回结果："1,2,1"
• 输入n=3，返回结果："1,2,1,3,1,2,1"

内容的提问来源于stack exchange，提问作者hyper