C 递归 详解(通俗易懂)

这篇具有很好参考价值的文章主要介绍了C 递归 详解(通俗易懂)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、定义

        1.概述

        2.条件

        3.比较

二、 如何理解递归?

        1.函数调用其他函数示例 : 

        2.函数调用函数自身示例 : 

        3.函数调用自身的底层操作 : 

                ①在主调函数调用被调函数之前——

                ②在被调函数返回主调函数之前——

                ③在出现多个函数相互调用的情况时——

三、递归的具体实例

        1.求1~100的和 : 

                思路 : 

                代码 : 

                优化 : 

        2. 汉诺塔问题 : 

                背景 : 

                思路 : 

                代码 : 

        3.斐波那契数 : 

                介绍 : 

                思路 : 

                代码 : 


一、定义

        1.概述

        递归(Recursion),又称递回,是指一个函数直接或间接地实现自调用。在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环。

        计算机科学家尼克劳斯·维尔特如此描述递归:

        “ 递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此,在计算机科学中,递归可以被用来描述无限步的运算,尽管描述运算的程序是有限的。

        ——尼克劳斯·维尔特

        2.条件

        递归必须设置一个明确的终止条件,当满足该条件时,递归停止;不满足该条件时,继续递归。PS : 如果一个递归没有设置终止条件,那么它会无限制地递归下去,形成死递归(类似于死循环),称为“死龟了”。

        一个使用了递归的函数,其处理的数据规模一定是在递减的。即,一个有效的递归,它的递归总次数是一定的,执行的次数越多,剩余的规模就越小。

        3.比较

        这里的“比较”,指的是递归和循环的比较

        理论上讲,可以用循环解决的问题都可以转化为用递归解决;但是用递归解决的的问题有时候并不能用循环解决

        递归结构简洁,更易理解,但是递归所需存储空间大,运行速度慢;

        循环结构复杂,不易理解,但是循环所需存储空间小,运行速度快。


二、 如何理解递归?

        1.函数调用其他函数示例 : 

                递归本质上利用的栈的原理,满足“先进后出”的特点。要想理解递归,必须先理解函数中是如何调用其他函数的,我们先来看下面一段代码 : 

# include <stdio.h>

void f1();
void f2();
void f3();

int main(void)
{
    f1();

    return 0;
}

void f1()
{
    f2();
    printf("AAAAA\n");
    return;
}

void f2()
{
    f3();
    printf("BBBBB\n");
    return;
}

void f3()
{
    printf("CCCCC\n");
    return;
}

                 你认为以上代码的输出结果是什么?输出结果如下 : 

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言

                解释 : 
                main函数先进栈,main函数中调用了f1函数,因此f1函数会进栈;因为f1函数中又调用了f2函数,因此f2函数接着进栈;又因为f2函数中又调用了f3函数,所以f3函数跟着进栈
                根据栈“先进后出”的特点,f3函数最后进栈,就要最先出栈,而f3中的代码执行完毕后,打印出CCCCC,继而返回f2中;f2函数执行完毕后,打印出BBBBB,接着f2出栈,返回f1中;f1再打印出AAAAA,最后f1出栈;所以出栈的顺序是f3 ——> f2 ——> f1
                那么递归其实就是把“函数中调用其他函数”,给变成了“函数中调用函数自己本身”,同样是栈的原理,同样满足“先进后出”的特点。

        2.函数调用函数自身示例 : 

                我们再来看一段简单的递归求某个数阶乘的代码,如下 : 

# include <stdio.h>

int factorial(int);

int main(void)
{
    int factorial_value = factorial(4);
    printf("4的阶乘 = %d", factorial_value);

    return 0;
}

int factorial(int n)
{
    if (n == 1 || n == 0)
        return 1;
    return n * factorial(n - 1);
}

                运行结果 : 

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言

                解释 : 

                首先我们可以看到,这段代码的目的就是求4的阶乘。main函数先进栈,main函数中调用了factorial方法(factorial [fækˈtɔriəl] 就是“阶乘”的意思),factorial方法要进栈,此时我们传入的实参 = 4;接着,因为4不满足factorial方法中if语句的判断条件,因此要执行return语句,而return语句的内容"n * factorial(n - 1)"中又调用了factorial函数自身,只不过这次调用的效果是factorial(3)了,所以factorial(3)方法中包含的局部变量要进栈;同理,factorial(2)方法包含的局部变量进栈;factorial(2)方法中有调用factorial(1)方法,所以factorial(1)方法包含的局部变量最后进栈。所以整个求4的阶乘的递归过程中,factorial函数的压栈顺序为:factorial(4) ——> factorial(3) ——> factorial(2) ——> factorial(1)
                在factorial(1)方法中,满足if条件语句,因此factorial(1)方法要返回1,接着,factorial(1)方法执行完毕,factorial(1)方法出栈,回到factorial(2)方法;factorial(2)方法返回 2 * factorial(1) = 2 * (1),接着factorial(2)方法出栈,回到factorial(3)方法;factorial(3)方法返回3 * (2 * 1),接着factorial(3)方法出栈,回到factorial(4)方法;factorial(4)方法返回4 * (3 * 2 * 1)。所以整个求4的阶乘的递归过程中,factorial函数的出栈顺序为:factorial(4) ——> factorial(3) ——> factorial(2) ——> factorial(1)。直到递归到factorial(1)时,停止递归,开始逐层返回。

                我们可以对以上代码进行优化,使得我们可以求任意一个数的阶乘,代码如下 : 

# include <stdio.h>

int factorial(int);

int main(void)
{
    printf("请输入你想求阶乘的数:(提示 : 大于等于0的整型数据)");
    int i;
    scanf("%d", &i);
    int factorial_value = factorial(i);
    
    if (factorial_value == -1)
        printf("请传入大于等于0的数!");
    else
        printf("\n所求数%d的阶乘= %d\n", i, factorial_value);

    return 0;
}

int factorial(int n)
{
    if (n < 0)
    {
        return -1;
    }
    else if (n == 0 || n == 1)
        return 1;
    return n * factorial(n - 1);
}

                运行效果 : (如下GIF图) 

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言

        3.函数调用自身的底层操作 : 

                ①在主调函数调用被调函数之前——

                 系统要将传入的实参和主调函数的地址等信息传递给被调函数保存。传递"主调函数的地址",其目的是为了确保程序执行的连续性,即当被调函数执行完毕准备出栈时,可以根据这个地址来找到接下来需要执行的语句。
                系统要为被调函数的局部变量(包括形参和方法体定义的变量)分配内存空间
               控制权限由主调函数转移到被调函数的入口,准备执行被调函数。

                ②在被调函数返回主调函数之前——

                系统要保存被调函数的返回结果,即对它做一个备份,用于返回给主调函数。
                系统要释放掉为被调函数分配的内存空间。(不包括动态内存)
                按照被调函数保存的返回地址,将控制权限由被调函数转移到主调函数

                ③在出现多个函数相互调用的情况时——

                按照“后调用,先返回”的原则,所涉及到的信息传递和控制转移等操作需要借助“栈”来实现。
                系统会将整个程序运行所需的内存空间安排在一个栈中,每当调用一个函数时,就在栈顶分配一块空间用于压栈;每当退出一个函数时,就释放这块区域,完成出栈操作;当前运行的函数永远位于栈顶的位置


三、递归的具体实例

        1.求1~100的和 : 

                思路 : 

                类似于上文中求阶乘的步骤,我们可以先进行一个if条件语句的判断——n是否等于1,该判断可作为递归结束的条件当n不满足等于1的条件时,就return n + f(n - 1),f代表当前求和的函数

                代码 : 

# include <stdio.h>

int sum(int);

int main(void)
{

    printf("\n1~100的和 = ");
    int sum_value = sum(100);
    printf("%d\n", sum_value);

    return 0;
}

int sum(int n)
{
    if (n == 1)
        return 1;
    return n + sum(n - 1);
}

                运行结果 : 

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言

                优化 : 

                我们可以令用户自定义传入sum函数的实参,达到求"1~n的和"的目的代码如下 : 

# include <stdio.h>

int sum(int);

int main(void)
{
    printf("请输入你想求的1到某个数的和:");
    int n;
    scanf("%d", &n);

    int sum_value = sum(n);
    if (sum_value != -1)
    {
        printf("\n1~%d的和 = ", n);
        printf("%d\n", sum_value);
    }
    else 
        printf("请输入合法的数字!");

    return 0;
}

int sum(int n)
{
    if (n < 1)
        return -1;
    else if (n == 1)
        return 1;
    return n + sum(n - 1);
}

                运行效果:(如下GIF图)

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言

        2. 汉诺塔问题 : 

                背景 : 

                传说越南河内某间寺院有三根银棒,上串 64 个金盘。寺院里的僧侣依照一个古老的预言,以特定规则移动这些盘子;预言说当这些盘子移动完毕,世界就会灭亡。移动金盘的规则如下——
                每次只能移动一个圆盘;
                大盘不能叠在小盘上面。
                设三根银棒分别为A,B,C;最终要将A棒上的64个金盘移动到C棒上,移动过程中可借助B棒来临时存放金盘。

                思路 : 

                仍是递归的思想——
                我们先从最简单的1个金盘说起,若想将一个金盘从A棒移动到C棒,直接移动就可以,不需要借助B棒。
                当A棒有2个金盘时,我们可以先将上面的第一个金盘放到B棒上;再把A棒的第二个金盘放到C棒;最后将B棒的第一个金盘放到C棒。(该目标的实现借助了B棒,B棒上临时存放了第1个金盘)
                当A棒有3个金盘时,我们可以设法将A棒上面的2个金盘放到B棒上,将第三个金盘从A棒移动到C棒,再设法将B棒临时存放的两个金盘放到C棒上。其中,“设法将A棒上面的2个金盘放到B棒上” 和 “设法将B棒上面的两个金盘放到C棒上” ,这两个步骤其实就是在重复②的步骤
                通过③我们可知,金盘的数量每增加1个,其实都是在重复之前金盘数量时的步骤,最核心的步骤就是将A棒最下面的那个最大的金盘从A棒放到C棒。而要想实现最核心的步骤,必须分三步走:先设法将A棒上面的n-1个金盘借助C棒移动到B棒,使A棒只剩下最下面的最大的金盘,同时C棒为空;这样才能 接着把最大的金盘从A移动到C;之后,再3° 设法将B棒上面的n - 1个金盘借助A棒移动到C棒

                代码 : 

# include <stdio.h>

int count = 0;
void hanoi(int, char, char, char);

int main(void)
{
    printf("请输入汉诺塔的层数, floors = ");
    int floors;
    scanf("%d", &floors);

    hanoi(floors, 'A','B','C');
    if (count > 0)
        printf("总共需要执行的步骤有%d步\n", count);

    return 0;
}

void hanoi(int n, char a, char b, char c)
{
    if (n < 1)
    {
        printf("请传入合法有效的数据!");
        return;
    }
    else if (n == 1)
    {
        printf("%c --> %c\n", a,c);
        ++count;
        return;
    }

    hanoi(n - 1, a,c,b);
    printf("%c --> %c\n", a,c);
    count++;
    hanoi(n - 1, b,a,c);

    return;
}

/*
    注意 : 
    ①hanoi(n - 1, a,c,b) 和 hanoi(n - 1, b,a,c),这两个步骤是相互联系的。
    ②else if语句中的printf语句,其目的是为了帮助完成hanoi(n - 1, a,c,b)操作;
     最后的printf语句,其目的是完成最核心步骤————将最大的盘从A棒移动到C棒。
*/

                运行效果 : (如下GIF图)

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言

        3.斐波那契数 : 

                介绍 : 

                Fibonacci[/ˌfɪbəˈnɑːtʃi/],斐波那契数(意大利语:Successione di Fibonacci),又译为菲波拿契数、菲波那西数、斐氏数、黄金分割数。所形成的数列称为斐波那契数列,又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列。这个数列是由意大利数学家斐波那契在他的《算盘书》中提出。
                在数学上,斐波那契数是以递归的方法来定义
                令F0 = 0; F1 = 1; 则Fn = F(n - 1) + F(n - 2),其中n ≥2。即——从数列的第三项开始,每一项的值等于前面两项之和,称为斐波那契数列。斐波那契数列的前几项如下所示 : 

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言

                PS : 0不是第一项,而是第零项,斐波那契数列在文本上从1开始。 

                思路 : 

                设n代表斐波那契数列的第n项,当n等于1或者等于2时,可以直接返回1当n大于2时,要想求出斐波纳契数列的第n项,必须知道它前面的两项分别是多少,而要想知道它前面的两项分别是多少,就又得知道这两项再分别往前的两项是多少依次递归下去,直到n == 1或者n == 2的情况时,return 1;接着再逐层返回,回到你想求出的第n项

                代码 : 

/*
    斐波那契数列
    2023.4.1
*/

# include <stdio.h>

int fibonacci(int);

int main(void)
{
    printf("请输入你想输出斐波那契数列的前几项?\nnum = ");
    int num;
    scanf("%d", &num);

    if (fibonacci(num) == -1)
    {
        printf("请输入合法数据!");
    }
    else 
    {
        int i;
        for (i = 1; i <= num; ++i)
        {
            printf("%d\t", fibonacci(i));
        }
    }

    return 0;
}

int fibonacci(int n)
{
    if (n < 1)
        return -1;
    else if (n == 1 || n == 2)
        return 1;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

                运行效果:(如下GIF图所示)

c语言递归,C,# 数据结构与算法(入门),数据结构,算法,递归,c语言文章来源地址https://www.toymoban.com/news/detail-745556.html

到了这里,关于C 递归 详解(通俗易懂)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-串-KMP算法详解(Next数组计算)(简单易懂)

    本文章就专讲kmp,暴力匹配就不讲了(我相信能搜索kmp的,暴力匹配算法应该也都了解过了) 为什么网上那么多讲kmp 我还发文章,很多文章我觉得讲的不是太通俗易懂,大多数我看起来都觉得有些懵逼 提示:以下信息来源百度 KMP算法是一种改进的字符串匹配算法,由D.E.K

    2024年02月06日
    浏览(43)
  • 【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟,并强制转换为 BTNode 型,用变量 node 来去管理开辟的空间。 我们初始化结点,其 val 即为传入的参数x,左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(43)
  • 数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)

    今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻

    2023年04月08日
    浏览(39)
  • 【数据结构】迷宫问题DFS非递归(c语言实现)

    本来之前写过一个推箱子,就想着写个迷宫游戏,因为想着推箱子游戏里面也有墙,也有玩家的移动,比推箱子简单的是还不用判断前面是否有箱子的情况,但是自己写的迷宫游戏如果自己随机生成的迷宫地图的话,不一定会有通路,他要学一个什么随机迷宫的生成,刚看完

    2024年02月08日
    浏览(38)
  • 数据结构与算法----详解二叉树的遍历(迭代、递归)

    ❤️ 作者简介 :大家好我是小鱼干儿♛是一个热爱编程、热爱算法的大三学生,蓝桥杯国赛二等奖获得者 🐟 个人主页 :https://blog.csdn.net/qq_52007481 ⭐ 个人社区 :【小鱼干爱编程】 🔥 算法专栏 :算法竞赛进阶指南 💯 刷题网站 :虽然市面上有很多的刷题网站,但是里面

    2024年01月24日
    浏览(51)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(66)
  • 数据结构(C语言):递归算法删除链表中所有值为x的结点

           这个标题为什么要叫“一个递归算法的诞生过程”呢?因为我在写这个算法的时候可谓一波三折,冲破重重Bug最终才得到了正确的算法。        所以在这里我和大家分享一下我写这段代码的整个过程。其中提到的一些问题大家可能写代码的时候也会遇到,所以建议

    2024年02月04日
    浏览(42)
  • 【数据结构初阶】十、快速排序(比较排序)讲解和实现(三种递归快排版本 + 非递归快排版本 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】九、排序的讲解和实现(直接插入 希尔 直接选择 堆 冒泡 -- C语言)

    2024年02月08日
    浏览(45)
  • 『初阶数据结构 • C语言』⑰ - 快速排序(hoare法、挖坑法、前后指针法与非递归实现)

    目录 1. hoare法 方法与步骤 代码实现 2. 挖坑法 方法与步骤 代码实现 3. 前后指针法 方法与步骤 代码实现  4. 快速排序的缺点与优化 1.快速排序的缺点 2.快速排序的优化 ① 三数取中法选 key 代码实现 ② 小区间优化 代码实现 5. 快速排序的非递归实现 附录﹡完整源码 快速排序

    2024年02月13日
    浏览(43)
  • 数据结构(C语言实现)——常见排序算法的基本思想及实现(快速排序的三种方法和优化及非递归实现快速排序)

    生活中几乎处处都会用到排序,比如:网购时的店铺顺序,学生成绩的排名等,今天我们就来学习数据结构中常见的几种排序算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列

    2023年04月24日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包