C++递归算法

C++ 中递归算法的示例与解释
计算阶乘
计算整数 n 的阶乘是一个经典的递归例子。阶乘定义为所有小于等于该正整数的自然数连乘的结果，特别地规定0! = 1。
#include <iostream>
using namespace std;

int factorial(int n){
if (n == 0 || n == 1) { // 基本情况
return 1;
}
return n * factorial(n - 1); // 递归调用
}

int main(){
int number;
cout << "Enter a positive integer: ";
cin >> number;
cout << "Factorial of " << number << " is " << factorial(number);
return 0;
}
登录后复制
上述代码展示了如何通过递归来实现阶乘运算[^2]。当输入数值较大时需要注意可能发生的栈溢出问题以及性能开销[^3]。
十进制转二进制
另一个常见的应用案例是从十进制到其他进制（这里以二进制为例）之间的转换：
void decToBin(unsigned long num){
if(num != 0){
decToBin(num / 2); // 对商继续做同样的操作直到其变为零为止
cout << num % 2; // 输出余数作为当前位上的值
}
}
登录后复制
此函数采用除基取余的方式逐步构建目标进制下的字符串表示形式，并借助于递归机制实现了自底向上的打印顺序调整。
使用递归进行快速排序
快速排序也是一种基于分治思想的经典排序算法，在适当优化的情况下可以达到O(n log n)的时间复杂度:
void quickSort(vector<int>&amp; nums, int low, int high){
if(low >= high) {
return ;
}

int pivotIndex = partition(nums, low, high);

quickSort(nums, low, pivotIndex-1); // 左侧部分再次执行相同逻辑
quickSort(nums, pivotIndex+1, high); // 右侧部分同样如此
}

// ...省略partition()的具体实现...
登录后复制
这段伪代码片段说明了怎样利用递归来完成整个列表元素的有效排列过程[^1]。
处理树形结构的数据遍历
对于像文件目录这样的层次化存储体系来说，递归提供了优雅的方式来访问每一个节点而不必担心具体细节层面的东西：
struct Node{
string name;
vector<Node*> children;
};

void traverse(Node* node){
cout << "Visiting " << node->name << endl;

for(auto child : node->children){
traverse(child); // 进入下一层级
}
}
登录后复制
这种模式非常适合用来探索具有嵌套特性的对象集合，比如XML文档解析器内部的工作原理就经常依赖于此[^4]。