龙空技术网

C++中的递归

编程小新 199

前言:

此时兄弟们对“递归算法的代码”大概比较关注,看官们都需要分析一些“递归算法的代码”的相关资讯。那么小编也在网摘上汇集了一些对于“递归算法的代码””的相关文章,希望我们能喜欢,咱们快快来了解一下吧!

1.概念

递归函数即自调用函数,在函数内部直接的或者间接地调用自己。在求解某些具有随意性的复杂问题时经常使用递归,如要求编写一个函数,将输入的任意长度的字符串反向输出。普通做法是将字符串放入数组中然后将数组元素反向输出即可,然而这里的要求是输入是任意长度的,总不能开辟一个很大的空间保存字符串吧?这时候递归就起作用了。递归采用了分治的思想,将整体分割成部分,从最小的基本部分入手,逐一解决,其中部分通常和整体具有相同的结构,这样部分可以继续分割,直到最后分割成基本部分。

递归函数必须定义一个终止条件,即什么情况下终止递归,终止继续调用自己,如果没有终止条件,那么函数将一直调用自己,知道程序栈耗尽,这时候等于是写了一个Bug!

总结递归的特点:

(1) 使用递归时,一定要有明确的终止条件!

(2) 递归算法解题通常代码比较简洁,但不是很容易读懂。

(3) 递归的调用需要建立大量的函数的副本,尤其是函数的参数,每一层递归调用时参数都是单独的占据内存空间,他们的地址是不同的,因此递归会消耗大量的时间和内存。而非递归函数虽然效率高,但相对比较难编程。

(4) 递归函数分为调用和回退阶段,递归的回退顺序是它调用顺序的逆序。

2.实践

斐波那契数列当n>3时,第n个元素的值等于第n-1个元素和n-2个元素的和,当n不确定具体数值时,可以通过递归的方式实现

int Fib(int n) { if (n < 2) return 1; return Fib(n - 1) + Fib(n - 2);}
void test_fib(int n) { int fib1[n], fib2[n]; fib1[0] = 1; fib1[1] = 1; fib2[0] = 1; fib2[1] = 1; for (int i = 2; i < n; i++) { fib1[i] = Fib(i); fib2[i] = fib2[i - 1] + fib2[i - 2]; } cout << "use func Fib() " << endl; for (int i = 0; i < n; i++) { cout << fib1[i] << ' '; } cout << endl; cout << "use for loop " << endl; for (int i = 0; i < n; i++) { cout << fib2[i] << ' '; } cout << endl;}

最终由递归得到的斐波那契数列和由for循环得到的数列相同。

阶乘问题同样可以通过递归实现,代码为

int Factorial(int n) { if (n == 1) return 1; return n * Factorial(n - 1);}

当n=5时,函数的调用过程如下图所示

汉诺塔问题是指一共有3根针,其中两根为空,另外一根针从上到下按照尺寸穿好了若干个盘子,上面的小下面的大,要求是每次移动一个盘子,将所有的盘子移动到另一根针上,并且所有的针上的盘子都满足上小下大的要求,如下图

这个问题同样可以使用递归的方式解决,思路如下

因此发现以上步骤实际上是一个重复的过程,则整个问题可以使用递归解决,当盘子个数为1时直接移动即可,为n时则先借助一根针将n-1个盘子移动到另一根针上,而n-1根针可以先移动n-1-1根针,如此往复。代码如下

void move(int n, char x, char y, char z) { // 将n个盘子从x借助y移动到z上 if (1 == n) { cout << x << "-->" << z << endl; } else { // 将n-1个盘子从x借助z移动到y上 move(n - 1, x, z, y); // 将第n个盘子从x移动到z上 cout << x << "-->" << z << endl; // 将n-1个盘子从y借助x移动到z上 move(n - 1, y, x, z); }}

最后,如果你想学C/C++可以私信小编“01”获取素材资料以及开发工具和听课权限哦!

标签: #递归算法的代码