【c语言】一篇文章搞懂函数递归

简介: 本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。

       函数递归,是令很多同学“谈虎色变”的话题。它出现时,总是让人摸不着头脑。接下来我将会详细讲解函数递归,让你对递归有新的认识。


一、递归的概念

       递归是什么?其实,递归是一种解决问题的方法,体现在c语言中就是函数自己调用自己。让我们举一个最史上最简单的递归代码:

#include<stdio.h>
 
int main()
{
    printf("hello world!\n");
    main();
    return 0;
}

上述代码当中,主函数main自己调用了自己,不难看出,这是一个死递归。主函数会无限调用自己,最终导致栈区内存不够而溢出,程序崩溃。不过这只是一个最简单的递归演示,真实的递归可不是这么使用的。


1.递归思想

       那么递归为什么会被使用呢?这就要提到递归思想了。递归思想,就是在解决一个难以求解的大型问题时,像剥洋葱皮一样,一层一层逐步推进,直到问题被解决。说白了,递归就是把大事化的过程。


2.递归的限制条件

       在我们刚才编写的代码当中,由于没有限制条件,所以主函数会不断地调用自己而导致栈溢出。所以一个递归的完成,限制条件是不可或缺的。当程序运行到满足这个限制条件的时候,递归就会停止。而每一次的递归,都会不断接近这个限制条件。我们在编写递归的时候,一定要先确定好限制条件


二、递归举例

       有了以上基础知识,接下来我会用一些例子来帮助大家理解递归的精髓。


1.求一个数的阶乘

       一个整数n的阶乘就是1~n之间的整数全部相乘。既然这样,那么我们就会想到:使用循环语句产生从1到n之间的所有整数,然后将他们全部相乘就可以了。好,我们先用代码实现:

#include<stdio.h>
 
int main()
{
    int n = 0;
    scanf("%d", &n);
    int i = 0;
    int ret = 1;//记录乘积
    for (i = 1; i <= n; i++)
    {
        ret *= i;
    }
    printf("%d\n", ret);
}

运行结果:



没错,5的阶乘就是120。那么,能不能用递归实现阶乘呢?


还记得求阶乘有一个公式吗?


n! = n * ( n - 1 )!


n的阶乘就是n乘n-1的阶乘。那么这里我们就可以用到递归思想了:为了求得n的阶乘,我们可以先求出n-1的阶乘,为了求得n-1的阶乘,我们需要求出n-2的阶乘......直到求出1的阶乘为止(因为1的阶乘就是1)


不过,我们好像遗漏了一个问题:0的阶乘是不是也是1?所以我们应该计算到0的阶乘为止,这样,用户输入0程序就不会出现问题了。


好了,让我们画一个简图便于我们创造出限制条件



接下来我们用代码实现一下:

#include<stdio.h>
 
int fact(int n)
{
    if (n == 0)
    {
        return 1;
    }
    if (n > 0)
    {
        return n * fact(n - 1);
    }
}
 
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", fact(n));
    return 0;
}

运行结果:



可以看出,运行结果是正确的。如果你还是难以理解,我们画一张图来显示它的详细流程:



程序前半部分逐层深入,从求5的阶乘深入到求0的阶乘,这个过程叫做递推,由于我们递归的限制条件是n==0,当计算到0的阶乘时,此层递归传入的参数刚好是0,满足条件,就不会继续深入了。这时候,1就是此层递归的返回值,便于前一层递归计算1的阶乘,直到最后得出最后结果。这个过程叫做回归


现在,想必你对递归已经有一定的认知了。不过,在这个例子当中,如果输入的数过大,会出现栈溢出的情况,因为每一次的递归深入都是在调用函数,而函数的调用是要消耗栈区的内存空间的。当内存空间被占满时,就会发生栈溢出。


2.打印一个整数的每一位

       接下来我们思考一下这个问题:用递归打印一个整数的每一位。我们都知道,对于一个一位数而言,它的每一位就是他自己,如果它超过一位,就要一个一个地得到它的每一位。


比如现在有一个数1234,1234%10就能得到个位数4,之后我们把1234/10,得到123,相当于去除了这个4,接着继续%10,就得到3,然后再/10,再%10...以此类推,在每一步都将得到的数打印出来,我们就可以分别打印出这个数地每一位。


有了基本想法之后,我们来想想限定条件:由于可以用取模的方法直接求得个位数,我们就将功能分为两步:第一步判断一个数是否是一位数,如果是就直接打印它,如果不是就对它除以10的结果进行判断。第二步,打印一个数%10的结果


接着,我们尝试用代码实现:

#include<stdio.h>
 
void Print(int n)
{
    if (n > 9)
    {
        Print(n / 10);
    }
    printf("%d ", n % 10);
}
 
int main()
{
    int n = 0;
    scanf("%d", &n);
    Print(n);
    return 0;
}

运行结果:



程序运行过程中,传入1234到函数当中,由于1234不是一位数,我们就将这个四位数拆解为打印123的每一位,并且打印出4,当进入123作为参数的递归时,将其拆解为打印12的每一位并且打印出3,直到得到1,递归就不继续进行,逐层深入解决问题。


我们再用流程图来表示以下整个过程:



按照这个流程,屏幕就会依次打印出1,2,3,4。如果你想要将这四个数倒着打印,那么只需要将printf函数写在判断语句之前即可。


       这样看来,递归是不是在某些情况下比循环更简单?如果这个程序用循环来写,那么就有很多细节需要处理。而使用递归的方法,虽然会牺牲一些运行效率,但是能够避免使用复杂逻辑,减少代码冗余,提高程序的简洁性


       接着,我们再来写一个程序:


3.求第n个斐波那契数

       首先来介绍一下什么叫做斐波那契数列。所谓斐波那契数列,就是说一个正整数数列,前两个数都是1,从第三个数开始,每一个数都是它之前的两个数之和。我们列举一下前几个数:1,1,2,3,5,8,13,21,34......


       我们从它的概念上入手:由于从第三个数开始每一个数就是它之前的两个数之和,言外之意就是我们可以求出它的前两个数,然后相加。如果前两个数不是第一,第二个数,就继续求下去。。。直到求到最开始的数为止。我们画一个简图来表示限制条件



这样是不是就感觉很简单了?我们来实现一下:

#include<stdio.h>
 
int fib(int n)
{
    if (n >= 3)
    {
        return fib(n - 1) + fib(n - 2);
    }
    if (n == 1 || n == 2)
    {
        return 1;
    }
}
 
int main()
{
    int n = 0;
    while (scanf("%d", &n) != EOF)//这里进行多组输入
    {
        printf("%d ", fib(n));
    }
    return 0;
}

运行结果:



三、递归的潜在问题

       对于之前求斐波那契数的程序,如果我们输入一个较大数字比如40,50等,你会发现它需要很久才能算出结果。这是为什么呢?由于我们的函数设计是要先求出前两个数,对于第50个斐波那契数,我们就要先求第48个数和第47个数,要求出这两个数,又要求第47个数,第46个数,第46个数,第45个数......这样就导致好多的数被重复计算了,而且计算次数是成指数级增长的。我们在刚才的代码中增加一个变量来记录一下第三个斐波那契数数被计算的次数

#include<stdio.h>
 
int count = 0;
 
int fib(int n)
{
    if (n >= 3)
    {
        if (n == 3)
        {
            count++;
        }
        return fib(n - 1) + fib(n - 2);
    }
    if (n == 1 || n == 2)
    {
        return 1;
    }
}
 
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    printf("%d次\n", count);
    return 0;
}

运行结果:



求第40个数的时候,第三个斐波那契数就被计算了三千九百多万次。这种计算量,就算是计算机也是心余力绌。在这种情况下,递归虽然易于写出,但是运行效率也太差了。我们尝试用循环来实现一下它:

#include<stdio.h>
 
int fib(int n)
{
    int a = 1, b = 1, c = 1;
    while (n >= 3)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}
 
int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d ", fib(n));
    return 0;
}

运行结果:




可以看出,运行结果与递归的方式是相同的,而且用时在包括调试时间的情况下也只有不到8毫秒。


       所以,递归虽好,但是有时候会出现运行效率低、栈溢出的情况。我们在使用的时候要合理考虑是否使用递归。


总结

       函数递归是一种解决问题的方法,它的表现形式是函数自己调用自己,核心思想是把大事化小。递归是有限制条件的,否则就会成为死递归。在编写程序的时候,一定要思考其限制条件。递归不是万能的,它可能出现运行效率低,栈溢出的情况。在编写程序时要根据实际情况进行思考是否使用递归。


       到这里,想必你对递归已经有了新的认知了吧!后续博主主要会与大家探讨指针方面的内容,感谢大家的支持❤❤❤

相关文章
|
2天前
|
存储 缓存 算法
【C语言】内存管理函数详细讲解
在C语言编程中,内存管理是至关重要的。动态内存分配函数允许程序在运行时请求和释放内存,这对于处理不确定大小的数据结构至关重要。以下是C语言内存管理函数的详细讲解,包括每个函数的功能、标准格式、示例代码、代码解释及其输出。
24 6
|
19天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明: 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数,即头文件中存在或已经定义过; 如果使用库函数,一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数,而且该函数与使用它的函数在同一个文件中,一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前,在函数的外部已做了函数声明,则在各个主调函数中不必多所调用的函数在做声明
31 6
|
2月前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
43 10
|
1月前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
2月前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
32 4
|
2月前
|
存储 C语言
【c语言】字符串函数和内存函数
本文介绍了C语言中常用的字符串函数和内存函数,包括`strlen`、`strcpy`、`strcat`、`strcmp`、`strstr`、`strncpy`、`strncat`、`strncmp`、`strtok`、`memcpy`、`memmove`和`memset`等函数的使用方法及模拟实现。文章详细讲解了每个函数的功能、参数、返回值,并提供了具体的代码示例,帮助读者更好地理解和掌握这些函数的应用。
27 0
|
2月前
|
C语言
【c语言】qsort函数及泛型冒泡排序的模拟实现
本文介绍了C语言中的`qsort`函数及其背后的回调函数概念。`qsort`函数用于对任意类型的数据进行排序,其核心在于通过函数指针调用用户自定义的比较函数。文章还详细讲解了如何实现一个泛型冒泡排序,包括比较函数、交换函数和排序函数的编写,并展示了完整的代码示例。最后,通过实际运行验证了排序的正确性,展示了泛型编程的优势。
23 0
|
2月前
|
算法 C语言
factorial函数c语言
C语言中实现阶乘函数提供了直接循环和递归两种思路,各有优劣。循环实现更适用于大规模数值,避免了栈溢出风险;而递归实现则在代码简洁度上占优,但需警惕深度递归带来的潜在问题。在实际开发中,根据具体需求与环境选择合适的实现方式至关重要。
31 0
|
4月前
|
机器学习/深度学习 C语言
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
要保持最小的步数,每一次汉诺塔问题(无论是最初还是递归过程中的),如果此时初始柱盘子数为偶数,我们第一步是把最上面的盘子移动到中转柱,如果为奇数,我们第一步则是将其移动到目标柱。
86 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
|
7月前
|
C语言
C语言递归问题【青蛙跳台阶】和【汉诺塔】
C语言递归问题【青蛙跳台阶】和【汉诺塔】