【C语言：递归思想】详解

老九君

发布于 2022-09-08 12:11:32

1.1K0

发布于 2022-09-08 12:11:32

文章被收录于专栏：老九学堂

关于递归，百度搜索给出了很多答案，无非就是递归是一种思想，其代码量少，但执行效率不高等等，但是讲道理合理地使用也能给我们带来较好的体验！

【递归思想】

递归的本质就是二字：套娃。什么被称之为是递归呢？在函数里面调用自身函数就被称之为是递归。而套娃实际上就是在函数中再次调用同样的函数。

以上便是递归的核心理念了，再来看你是否把这个核心理念完整的刻在你的脑海当中去。

在编程语言当中我们知道，一个函数是可以调用另一个函数的，那么有个特例如下：

如果函数调用了自己，我们便把函数在运行的时候调用自己的情况叫做是递归。用一个简单的例子来进行说明：

那么我们现在假设分析下f(3)当中的结果到底是什么如下：

1、当参数x的值等于③的时候，开始进入这个函数。此时这个函数返回值是 ③ + f(②)。

注:把x的值给带入到f()函数当中去，尽管返回值的参数是不一样的。也一样带进去即可。

那么我们会知道③是一个确定的数值，那么f(②)它是一个不确定的值，又会等于多少？

2、当函数的参数为②的时候，它的返回值就是 ② + f(①)。

3、以此类推下去，参数x值为①的时候，函数的返回值就是 ① + f(0)。

在上述的代码中我们可以知道，没有判断条件，这种调用是永远都不会停止的。

所以，我们需要在函数当中加入一个判断语句，决定何时停止调用自己。

代码示例如下：

【计算1加到100结果】

想必你看完上述对递归的讲解，相信已经明白了递归的大致思想了。那么接下来就来用递归做一道sum求1+2...100的求和。

示例代码如下：

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>int f(x){  if (x == 0)    return 0;  else    return x + f(x - 1);}int main(void){  int sum = f(100);  printf("sum = %d\n", sum);  return 0;}

运行结果：sum = 5050

代码解析：

在这里我们只需要把f(x)当中上述的3改成100就可以了。

f(100) = 100+f(99) = 100+99+f(98).....f(0) = 100+99+98+....+0 = 5050 || 0+...1+2+3...=5050

注:return x + f(x-1) 返回结果会返回到 f(x) 当中，第一次 x = 100 f(x-1) = 99 返回到 f(x) 当中运算符("+") 100 + 99，此时，f(x) = 199 + f(98) 依次循环执行，直到最终x==0的时候便停止调用。

递归条件：

1、存在限制条件，当满足这个限制条件之后的时候，递归便会不再继续。

2、每次递归调用之后都会越来越接近这个限制条件。

递归，有递就有归，只递不归会导致程序崩溃。为了避免这种情况递归一定是要包含条件语句的。

【栈(stack)】

在执行函数的时候，函数内部局部变量的存储单元都是可以在栈上进行创建的，函数执行结束的时候这些存储单元会被自动的进行释放。

栈区主要存放运行函数所分配的局部变量、函数的参数、返回数据、返回地址等。

注意：递归是必须要存在着限制条件的，不然堆栈当中就会产生栈溢出。在程序运行的时候，调用函数是有代价的。

那就是需要占用一片叫做栈(stack)的内存空间。当调用函数的时候，都必须要存放到一些数据到栈里面去。

当函数运行结束的时候这些数据会从栈里面被取出。那么我们知道如果调用了很多函数但是这些函数都不会被返回的

那么栈就会被塞满了，数据就没有地方存放了，这种情况就叫做栈溢出的错误，程序也会被操作系统强行终止。

关于【计算3的阶层】，示例代码如下：

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>int f(x){  if (x <= 1)    return 1;        //return x;  else    return x * f(x - 1);}int main(void){  int sum = f(3);  printf("sum = %d\n", sum);  return 0;}

运行结果：sum = 6

代码解析：

是不是发现上述计算1加到100结果和这道题目是做法非常类似的，只不过改变了调用的运算符，以及限制条件。