发疯的技术鼠头像
第09篇-函数递归封面图

第09篇-函数递归

在这里插入图片描述


个人主页: 发疯的技术鼠

❄️专栏传送门:《C语言》《数据结构》《C++》《算法》《Linux系统》
🌟Gitee仓库:《C语言与数据结构与算法》《C++》
在这里插入图片描述

第 9 篇:函数递归

一句话先记住:递归就是函数自己调用自己——把大问题拆成同款小问题往下"递",碰到出口再一层层把答案"归"回来。

在这里插入图片描述


写在前面:一个用循环写起来很别扭的小问题

给你一个整数 1234,要求按顺序打印出它的每一位:1 2 3 4。你会怎么写?

第一反应肯定是取余:1234 % 10 得 4,1234 / 10 得 123,再 % 10 得 3……这么一路取下去,四位数字轻轻松松全拿到。

问题只有一个:顺序是反的。 你得到的是 4 3 2 1。

想让它顺着来,用循环就得拐个弯:先把每一位倒着存进数组,再把数组倒着遍历一遍;或者干脆把整个数先倒过来。能写,但写起来一点都不"自然"。

换一个念头,事情就不一样了:想打印 1234 的每一位,能不能先打印 123 的每一位,最后再打印 4?

4 是最好拿的一位,却偏偏要留到最后才打印;而"打印 123 的每一位"和"打印 1234 的每一位",是同一个问题,只是规模小了一圈。

顺着这句话往下问,问到最后只剩一位数——它自己就是答案。然后一层层回来,1 2 3 4 就顺着出来了。

这就是递归。它没给你任何新语法,只是允许你写出像"套娃"一样的代码:在函数里调用函数自己。听起来玄,写起来短,坑也深。


一、递归:函数自己调用自己

递归(recursion)这个词,拆开看特别直白:递是递推,归是回归。

  • 递推:把一个大型复杂的问题,层层转化成一个和原问题相似、但规模更小的子问题;
  • 回归:拆到不能再拆的时候停手,再一层层把结果带回来。

所以递归的思考方式,说穿了就四个字:大事化小。

1.1 史上最简单的递归:main 调用 main

在 C 语言里,函数自己调用自己是完全合法的。不信你看:

#include <stdio.h>

int main()
{
    printf("hehe\n");
    main();      // main 函数里又调用了 main 函数
    return 0;
}

这段代码能编译、能运行。但你会看到屏幕上的 hehe 一行接一行地往下刷,刷到你根本来不及按 Ctrl+C——然后程序"啪"地一声退出,VS 2022 弹出来的提示是栈溢出(stack overflow,异常代码 0xC00000FD)。
在这里插入图片描述

这段叫"只是演示递归的基本形式,不是为了解决问题"。这话很客气,翻译一下就是:它是个死递归。

为什么会溢出?因为每一次函数调用,系统都要在内存的栈区给它准备一小块空间,用来放这次调用的参数、局部变量和返回地址,这块空间叫函数栈帧(stack frame)。函数不返回,栈帧就一直占着不收。main 调 main,一层套一层,栈帧叠上去永远不回收,而栈就那么点大——叠穿了,程序就崩。

栈帧的账第五节再细算,现在你只要记住:递归不是免费的,每深一层都要付一块内存。

1.2 递归的两段路:先下去,再上来

在这里插入图片描述

上面这张图,是理解递归最重要的一张:递归 = 递推 + 回归。

只有"下去"、没有"上来"的,不叫递归,叫死循环的另一种写法。只有"下去"接着"上来"、最后给出结果,才是一次完整的递归。

这个感觉,跟你小时候在宿舍问"晚上吃啥"一模一样:

💡 比喻:你问室友,室友说"我也不知道,我问问隔壁"。隔壁再问隔壁……一直问到最后一个哥们儿拍板:"火锅。"然后这个答案沿着刚才问过来的路,一层层传回到你耳朵里。往下问是递推,火锅传回来是回归。


二、两个必要条件:一个都不能少

写递归时,有两个条件必须同时满足,缺一个就是死递归。

在这里插入图片描述

条件一:存在限制条件,也就是"出口"。 满足这个条件的时候,递归不再继续,直接返回一个确定的值。

条件二:每次调用之后,都越来越接近这个限制条件。 每调一次,问题的规模必须真的在变小。

第一个条件好理解——总得有个"到底了"的地方。第二个才是重灾区:它要求每一次调用都真的更靠近出口,而不是"看起来在变小"。

拿阶乘举例。正常写法里,Fact(n) 调的是 Fact(n - 1),n 每次减 1,迟早减到 0,出口就到了。

可要是你手一抖,写成这样:

int Fact(int n)
{
    if (n == 0)
        return 1;
    else
        return n * Fact(n);   // 这段是错的:n 永远不变,出口永远等不到
}

编译能过,逻辑上却是在原地打转:Fact(5) 要等 Fact(5),Fact(5) 又在等 Fact(5)……出口明明写着,你就是走不到,最后还是栈溢出。
在这里插入图片描述

⚠️ 踩坑预警:“写了 if"不等于"有出口”。 出口的条件必须真的会出现,而且每一次调用都必须真的朝它挪了一步。检查递归写没写对,就问自己两个问题:① 它在什么情况下停?② 凭什么保证它一定会停?这两个问题答不上来,代码迟早崩。


三、例 1:求 n 的阶乘

阶乘(factorial)的定义:一个正整数的阶乘,是所有小于及等于该数的正整数的积,记作 n!;另外单独规定 0! = 1。

它天生就是递归的,因为:

n! = n × (n - 1)!

验算一下:

5! = 5 × 4 × 3 × 2 × 1
4! = 4 × 3 × 2 × 1
所以:5! = 5 × 4!

"求 5 的阶乘"和"求 4 的阶乘"是同一类问题,后者只是规模小了一圈。一直小下去,就小到那个特殊值 0! = 1——出口到了。

写成公式:

Fact(n) = 1                , n == 0
Fact(n) = n * Fact(n-1)    , n > 0

代码几乎是照着公式抄下来的:

#include <stdio.h>

int Fact(int n)
{
    if (n == 0)
        return 1;                // 出口
    else
        return n * Fact(n - 1);  // 逼近
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fact(n);
    printf("%d\n", ret);
    return 0;
}

输入 5,输出 120,函数体就 6 行。
在这里插入图片描述

在这里插入图片描述

它到底是怎么算出 120 的?把 Fact(5) 摊开来看:

Fact(5) = 5 * Fact(4)
        = 5 * 4 * Fact(3)
        = 5 * 4 * 3 * Fact(2)
        = 5 * 4 * 3 * 2 * Fact(1)
        = 5 * 4 * 3 * 2 * 1 * Fact(0)
        = 5 * 4 * 3 * 2 * 1 * 1
        = 120

注意这两个方向:

  • 前 5 行是递推:Fact 一层层往里钻,每一层都还没算出结果,只能先把 n 挂在那儿等;
  • 后面几行往回乘是回归:Fact(0) 交出 1 之后,Fact(1) 才有东西可乘,Fact(2) 才有东西可乘……

Fact(5) 在等 Fact(4) 的时候,从 Fact(5) 到 Fact(0) 这 6 层是同时存在的:递归并没有"省掉"空间,它只是把循环要用的空间,挂到了栈上。

⚠️ 踩坑预警:别拿 int 算太大的阶乘。12! = 479001600 还在 int 范围里,而 13! = 6227020800 已经超过 int 的上限 2147483647 了。输入 13,你会得到一个"看起来挺像"的错误答案——这不是递归的错,是类型装不下。课件题目里那句"不考虑溢出",就是这个意思。


四、例 2:顺序打印一个整数的每一位

回到开头那个问题:输入 1234,输出 1 2 3 4。

4.1 先用循环想一想

% 10 拿最低位,/ 10 删掉最低位,这两步配合,就能把每一位都揪出来:

#include <stdio.h>

int main()
{
    int n = 1234;
    while (n > 0)
    {
        printf("%d ", n % 10);
        n /= 10;
    }
    return 0;
}

输出 4 3 2 1。位数一个不少,顺序全反了。
在这里插入图片描述

原因很简单:4 是第一个被算出来的,所以第一个被打印;可它偏偏该排在最后。

4.2 换个问法:能不能先别打印

假设有个函数 Print(n),它的本事就是"打印 n 的每一位"。那 Print(1234) 要干的事,可以拆成两步:

  1. 先让 Print(123) 把 123 的每一位打印完;
  2. 然后自己打印最后那一位 4。

4 怎么来?1234 % 10。123 怎么来?1234 / 10。

而 Print(123) 又能拆成 Print(12) 加打印 3,Print(12) 再拆成 Print(1) 加打印 2。

拆到 Print(1) 的时候,1 已经是一位数了,不用再拆,直接打印,这一层就是出口。

在这里插入图片描述

注意图里最右边那一列:Print(1234) 是最先调用的,却最后一个打印。为什么?因为它调完 Print(123) 就一直挂在那儿等着,等下面三层全部打完返回,它才轮到自己执行那句 printf。

所以打印的顺序,正好和调用的顺序反过来——这就是输出能是 1 2 3 4 的原因。

代码写出来,短得让人意外:

#include <stdio.h>

void Print(int n)
{
    if (n > 9)               // 不是一位数,才需要再拆
    {
        Print(n / 10);       // 先把前面几位处理完
    }
    printf("%d ", n % 10);   // 再打印自己这一位
}

int main()
{
    int m = 0;
    scanf("%d", &m);
    Print(m);
    return 0;
}

输入 1234,输出 1 2 3 4 (每个数字后面跟一个空格)。输入 520,输出 5 2 0 。
在这里插入图片描述

这个 if (n > 9) 就是出口的另一种长相:它没有 return,只是把"继续拆"这个动作挡在了门外。出口不一定要 return,只要能让递归不再往下调,它就是出口。

4.3 一个开关:printf 放哪,决定正序还是倒序

这是理解递归最省力的一个观察点。

同一句 printf,放在递归调用后面,输出正序;挪到递归调用前面,立刻变倒序:

在这里插入图片描述

只有一行代码的位置变了,输出就从 1 2 3 4 变成 4 3 2 1。

💡 理解:递归调用像一道传送门。代码写在传送门后面,意思是"等你回来我再干";写在前面,意思是"我先干了再说"。同一个函数,两种性格。

⚠️ 踩坑预警:这个 Print 只对非负整数成立。输入 -1234,n > 9 一开始就不成立,函数直接跳到 printf("%d ", n % 10);而 C 语言里负数的取余结果跟着被除数走,-1234 % 10 是 -4,最后屏幕上只有一个 -4。要支持负数,得先单独打一个负号,再把数转成正数继续拆——这是"看起来能跑"和"真的正确"之间的距离。


五、递归与迭代:不是谁更高级,而是谁更合适

递归是很好的编程技巧,但技巧都有代价。

5.1 代价:每一层都占一块栈

栈帧这笔账,这里一次算清楚:

  • 每次函数调用,都要在栈区申请一块空间,存参数、局部变量、返回地址;
  • 函数不返回,它的栈帧就一直被占着;
  • 递归每深一层,就多一块栈帧挂着,直到开始回归才逐层释放。

所以递归的深度是有上限的,而且这个上限你说了不算——它取决于编译器和系统给栈留了多大。普通桌面程序留给栈的空间通常也就 1 MB 到 8 MB,层次一旦深到十万量级,栈基本就撑不住了。

💡 简化:递归调用就像上楼时每层留一个人帮你盯梢。三五层没事,几百层还行,上万层就把楼道挤爆了。栈溢出,就是楼道挤爆了。

5.2 阶乘:换成循环,又快又省

阶乘的本质是"1 到 n 累乘",那用循环写最直接:

int Fact(int n)
{
    int i = 0;
    int ret = 1;
    for (i = 1; i <= n; i++)
    {
        ret *= i;
    }
    return ret;
}

一个变量 ret,一个循环,从头乘到尾,不需要任何栈帧叠加。这种"用循环代替递归"的写法,就叫迭代(iteration)。

同样的任务,迭代的空间开销是常数级,递归是线性级;n 一大,递归就先被栈拦住了。

5.3 斐波那契:递归的反面教材

有更极端的例子。斐波那契数列(Fibonacci sequence)的递推式特别诱人:

Fib(n) = 1                    , n <= 2
Fib(n) = Fib(n-1) + Fib(n-2)  , n > 2

看到这个式子,手会不受控制地写出:

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

代码是对的,结果也是对的。但它慢得离谱:n 从 40 加到 50,计算量涨了 120 多倍。课件里那句"需要很长时间才能算出结果",说的就是这个。

慢在哪儿?慢在重复计算。Fib(5) 要算 Fib(4) 和 Fib(3);而 Fib(4) 里面又要再算一遍 Fib(3)——同一个 Fib(3),被算了好几次。层数越深,重复越多,而且是指数级地多。

加个计数器,专门数 Fib(3) 被算了多少次:

#include <stdio.h>

int count = 0;

int Fib(int n)
{
    if (n == 3)
        count++;                    // 数一数 Fib(3) 被算了几次
    if (n <= 2)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    printf("\ncount = %d\n", count);
    return 0;
}

输入 40,结果是 102334155,而 count = 39088169。
在这里插入图片描述

一个 Fib(3),区区等于 1 的小数,被翻来覆去算了三千九百零八万八千一百六十九次。

、在这里插入图片描述

这个数字其实不神秘。设"算 Fib(n) 时 Fib(3) 被调用的次数"为 c(n),那么 c(n) = c(n-1) + c(n-2)——它和斐波那契自己的递推式长得一模一样。所以 c(40) 恰好就是斐波那契数列的第 38 项,也就是 39088169。

这就是"递归写法漂亮、跑起来要命"的典型:公式是递归的,不代表实现就该递归。

5.4 换迭代:两个变量就够

斐波那契的本质是"前两个数加起来得到第三个,然后往后挪一格"。那就从前往后算,别回头:

int Fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;
    while (n > 2)
    {
        c = a + b;   // 新的第三项
        a = b;       // 窗口整体后移一格
        b = c;
        n--;
    }
    return c;
}

a、b 是相邻两项,c 是它们加起来的新项;算完把窗口往后挪一格,n 减 1,直到只剩最后两项。

这个写法从头到尾只用了三个变量,没有任何重复计算。不过别高兴太早:Fib(47) = 2971215073,已经超出 int 的上限了,这时候慢已经不是最大的问题,溢出才是。

5.5 那到底该挑哪个

对比项递归迭代(循环)
代码长度短,几乎照着公式抄稍长,要想清楚从哪儿开始、到哪儿结束
可读性问题本身是递归定义时,一眼就懂线性累加类问题,一眼就懂
空间开销每深一层多一块栈帧,可能栈溢出通常只用几个变量
时间开销有函数调用的额外开销;重复子问题时指数级一般更省
适合的场景树、汉诺塔、快排、归并排序这类"天生递归"的问题累加、累乘、遍历这类线性问题

结论不是"递归不好",而是:

当一个问题的子问题结构复杂到用循环根本写不明白时,递归的简洁性值得那些开销;反过来,能用一次循环写清楚的问题,别硬套递归。


六、什么时候该用递归

综合前面的例子,判断标准其实只有三条:

  1. 问题本身是递归定义的——大问题能直接拆成同款的、更小的自己。阶乘、斐波那契、汉诺塔、树的遍历、快排、归并排序,都是这一类;
  2. 深度可控——几十层、几百层这种量级,栈扛得住;
  3. 没有大量重复子问题——否则递归展开出来的计算量会失控,斐波那契就是活教材。

反过来说,遇到下面这些情况,别犹豫,写循环:

  • 线性问题:累加、累乘、统计、遍历一遍数组;
  • 深度不可控:比如递归遍历一条很长的链表,长度上万就可能爆栈;
  • 有明显重复子问题,又没做记忆化(把算过的结果存起来)。

最后留两个拓展题:青蛙跳台阶(一次跳 1 级或 2 级,跳上 n 级有多少种跳法,本质还是斐波那契)和汉诺塔(n 个盘子的最少移动步数是 2 的 n 次方减 1)。都是练"大事化小"的好题。

⚠️ 踩坑预警:不要迷恋递归。很多教材用递归来解释问题,是因为讲起来清晰,不是因为跑起来更快。真正落地时,"能迭代就迭代,递归留给那些天生递归、深度又可控的问题"是一条很实用的经验。


写在最后

这一篇只有一条主线:

能把大问题拆成"同款的、更小的自己" → 一定有一个出口 → 每次都必须朝出口挪一步 → 拆的过程要付栈空间 → 所以该迭代时就别硬递归。

你会发现,递归并不难写,难的是相信它。刚学的人总想在脑子里把每一层都展开一遍,Fact(5) 还行,到了汉诺塔脑子就炸了。正确的姿势是:只验证"这一层"和"下一层"的关系,剩下的交给函数自己去操心。

下一篇我们进入 操作符详解——&、|、^、~、移位、优先级、结合性,还有那些"看起来一样、结果完全不同"的表达式。到时候你会发现,很多你觉得"玄学"的 bug,根子都在操作符的优先级和求值顺序上。

所有伟大的坚持,背后都是平凡的日复一日。

📚 本篇导航:第 8 篇:VS 实用调试技巧 | 第 10 篇:操作符详解

转载自 CSDN-专业IT技术社区

原文链接:https://blog.csdn.net/xxw20050929/article/details/171044437

文章来源转载

评论

评论列表

微信小程序
QQ小程序

关于作者

点赞数:0
关注数:0
粉丝:0
文章:0
关注标签:0
加入于:--