2024年6月2日发(作者：)

c++ 递归算法经典实例详解

递归算法是一种通过重复调用自身来解决问题的编程方法。在C++中，递归可以用于解决各

种问题，例如排序、搜索、树遍历等等。下面是一个经典的递归算法实例：斐波那契数列。

问题描述：给定两个整数n和m，求第n个斐波那契数列的值fn，其中fn=mfn-1+fn-2 (n>1)，

fn=m (n=1)，fn=0 (n=0)。

以下是用C++实现的递归算法：

c

#include

using namespace std;

int fibonacci(int n, int m) {

if (n == 0) {

return 0;

} else if (n == 1) {

return m;

} else {

return fibonacci(n-1, fibonacci(n-2, m));

}

}

int main() {

int n = 10, m = 2;

cout << "The " << n << "th Fibonacci number is: " << fibonacci(n, m) << endl;

return 0;

}

解释：在上面的代码中，我们定义了一个名为fibonacci的函数，该函数采用递归方法来计

算第n个斐波那契数列的值。如果n等于0，则返回0；如果n等于1，则返回m；否则，我们可

以通过递归调用fibonacci函数来计算fn-1和fn-2的值，并将它们相加得到fn的值。在main

函数中，我们定义了n和m的值，并调用fibonacci函数来计算第n个斐波那契数列的值，并输

出结果。

需要注意的是，递归算法虽然简单易懂，但是可能会导致栈溢出等问题。因此，在使用递归

算法时需要谨慎考虑递归深度等因素。