吃透C语言递归：三大经典题目统一思维与拓展

前言初学递归我们最容易陷入的误区大多是死抠每一层递归的执行细节越看越乱实际上所有基础递归问题共用一套通用核心思想也是我总结的本质大事化小正难则反倒推拆解问题触达边界后回溯合并结果不需要正向模拟复杂过程只需要思考大问题能不能拆成小问题最小的已知边界是什么子问题如何合并成原问题答案本文统一梳理斐波那契数列、青蛙跳台阶、汉诺塔三大递归经典题以及尾递归的拓展彻底打通递归底层逻辑并附完整可运行的C语言代码一. 递归核心思维分三步解题正难则反不正向枚举所有情况从“最后一步”倒推大事化小将n规模问题拆解成n - 1 / n - 2的子问题边界兜底找到最小、已知答案的初始情况递归到此停止逐层回溯计算大多数递归题目基本上都遵循这套规则二. 题型一斐波那契数列求第n项问题描述斐波那契数列1、1、2、3、5、8 …规律从第三项开始每一项等于前两项之和求斐波那契数列的第n项是多少递归思维拆解我们知道正向去求第n项比较难要么需要使用迭代让数值不断平移去解决问题迭代法后面会讲到要么就需要一些偏数学的知识比如斐波那契数列的通项公式抑或是通过递推矩阵和快速幂加速计算来算出最终结果这些方法都是可行的不过我们本文的重点是递推这里就不做过多展开了正向不好去思考的话那有没有什么别的办法能更简单地解决问题呢其实我们可以反向去思考一下我们拟定一个函数命名为fib后续为了方便我们就叫它函数F假设我们想算一下斐波那契数列的第五项是多少不难看出当n 3 时求F(n) → 等价于求 F(n - 1) F(n - 2)相当于把这个函数拆分成了两个“更小”的函数也就意味着我们把它拆成了两个更小的子问题即求F(n - 1) 和 F(n - 2)而F(n - 1) 和 F(n - 2)依旧可以继续向下拆分一直递推下去最终会落到已知初始边界F(1) 1F(2) 1让F(1)和F(2)依次回归最终就能依次算出F(3)F(4)以及F(5)总的来说程序会先不断向下递推直到触达边界条件再从下往上回归把结果逐层相加最终就能算出F(n)逻辑如下回归过程递推过程Fib(5)Fib(4)Fib(3)Fib(4)Fib(3)Fib(2)Fib(3)Fib(2)Fib(1)Fib(3)Fib(2)Fib(1)Fib(2)1Fib(2)1Fib(1)1Fib(3)2Fib(4)3Fib(5)5Fib(3)2也就是说我们只需要让Fib函数自己调用自己程序想计算F(5)那就要先计算出F(4)和F(3)想计算出F(4)和F(3)就要先计算出F(3)F(2)和F(1)而F(2)和F(1)是已知的程序也就可以开始进行回归了.c代码实现如下#define_CRT_SECURE_NO_WARNINGS#includestdio.h//斐波那契数列intFib(intnum){if(num1||num2){return1;}else{returnFib(num-1)Fib(num-2);}}intmain(){intnum0;scanf(%d,num);intresultFib(num);printf(第%d项为%d\n,num,result);return0;}三. 题型二青蛙跳台阶求跳法总数问题描述一只青蛙一次可以跳1级台阶或跳2级台阶求跳到第n级台阶的总方法数是多少递归思维拆解同样的思路核心是同源的我们不好去从正面计算出到底有多少种跳法但反着来看我们可以从最后一步最后一跳开始看跳到第n级台阶最后一步只有两种可能要么最后跳1级前面需要先跳到第n - 1级要么最后跳2级前面需要先跳到第n - 2级所以总跳法 跳到第n - 1级的方法数 跳到第n - 2级的方法数我们依旧把这个大问题拆成了两个子问题而这两个子问题又可以继续拆分一直拆到“跳到第1级的方法数”和“跳到第2级的方法数”这两个边界条件那就很容易了跳到第一级只有一种方法就是跳一级跳到第2级有两种方法就是跳1级再跳1级或者是直接跳2级我们不难发现这个所谓的“青蛙跳台阶”问题唯一和斐波那契数列的区别就是初始边界有差异但它和斐波那契数列的递推结构是完全一致的这里我们直接来实现.c代码#define_CRT_SECURE_NO_WARNINGS#includestdio.h//青蛙跳台阶问题intFrogJumps(intnum){if(num1)return1;if(num2)return2;returnFrogJumps(num-1)FrogJumps(num-2);}intmain(){intnum0;scanf(%d,num);intresultFrogJumps(num);printf(青蛙跳到第%d个台阶的跳法有%d种\n,num,result);return0;}四. 题型三汉诺塔问题求最少移动次数问题描述三根柱子A起始、B中转、C目标将n个从小到大堆叠的盘子从A全部移动到C大盘子不能压小盘子一次只能移动一个盘子求盘子从A移动到C的最少移动次数2.递归思维拆解这个问题会把很多朋友吓退认为有些复杂难以用编程语言去实现但其实我们依旧可以用递归的思想去解决这个问题n个盘子移动情况的确有些复杂那我们能不能把它也拆成多个子问题呢我们会发现我们可以把上方n - 1个盘子借助目标柱C从柱A移到中转到柱B随后我们把最底下最大的1个盘子直接从柱A移到柱C仅一次最后我们把柱B上n - 1个盘子借助起始柱A移到目标柱C我们把这个问题再次拆成了两个子问题移动n - 1个盘子 一次底盘移动这必然也会持续拆分到n 1的最小边界但这里一定会有一个问题出现凭什么能直接把n - 1个盘子当成一个整体移走规则不是“一次只能移动一个盘子”吗这是很多朋友都会有的问题而破局的关键在于递归的精髓就是把复杂问题“降维”了在更小的问题里原来的难题就消失了什么意思呢其实就是说“移动n - 1个盘子”这个动作并不是真正意义上的“一次性”的而是一个递归调用的子问题而我们是无条件信任“n - 1个盘子的移动”是有解的我们不用关心它具体怎么移那是另一个问题**我们只需要知道它“能移走”**这就像我们用一个已经写好的函数我们有时候不需要知道它的内部实现只需要知道它实现的如果正确那么就能返回正确结果并且这一步一定不是直接把n - 1个盘子丢过来而是程序会进入一个新的子问题“如何把n - 1个盘子从A柱移到B柱”而这个问题也不会直接得到答案这个子问题会继续递归拆分成更小的问题直到移动1个盘子的简单情况整个过程是完全遵循“大盘子不能压小盘子”这个规则的所以每一步的移动都是合规的所以我们实现代码时我们可以定义一个HanoiTower函数要先把上层n - 1个盘子挪走消耗HanoiTower(n - 1)一次底部大盘固定移动固定消耗一次再将n - 1个盘子挪至目标位置再次消耗HanoiTower(n - 1)一次这里我们就可以实现.c代码了#define_CRT_SECURE_NO_WARNINGS#includestdio.h//汉诺塔问题intHanoiTower(intnum){if(num1){return1;}return2*HanoiTower(num-1)1;}intmain(){intnum0;scanf(%d,num);intresultHanoiTower(num);printf(实现%d层汉诺塔至少需要%d步\n,num,result);return0;}五. 迭代与递归的选择与拓展至此我们已经完整实现了三个经典递归题目我们前面提到斐波那契数列也是可以通过迭代让数值不断平移去解决问题我们就以斐波那契数列为例进行探讨接下来我们直接提供一段非递归的斐波那契数列代码运行一下让我们直观感受一下两者的差别#define_CRT_SECURE_NO_WARNINGS#includestdio.hintFib(num){if(num1||num2){return1;}inta1;intb1;intres;for(inti3;inum;i){resab;ab;bres;}returnres;}}intmain(){intnum0;scanf(%d,num);intresult1Fib(num);printf(第%d项为%d\n,num,result1);return0;}我们先来运行一下递归模式的代码以输入50举例我们会发现递归状态下算出的结果非常慢短时间是计算不出来的它在运行吗我们打开任务管理器发现它确实在运行这个程序占着我们的CPU和内存而我们反观迭代状态下几乎是瞬间算出了答案哪怕整形变量溢出导致算的结果是错误的但运行速度也是非常快的为什么相信大家也都知道是因为函数不断在栈帧上申请空间需要申请的函数空间多达2^49这个数量级虽然递归程度不深但这个数据无疑是很恐怖的重复计算非常多。相比于迭代的迅速平移计算只需要计算50次即可明显递归要慢很多可以看出普通递归是有两个致命问题的1. 栈帧是在不断积累的很容易导致栈溢出的现象因为上一层的栈帧不能销毁必须一直保留2. 普通的递归是有海量重复计算的拖慢程序的运行速度有没有什么方法解决这个问题这里我们需要用到一个递归的拓展尾递归那么尾递归是什么简单来说就是一个递归函数在它的所有分支里最后一步操作只能是“调用自身”并且调用后不能再做任何计算、赋值等操作直接把返回值交给上一层为什么要这么写尾递归的本质是什么尾递归的写法是为了让编译器能做尾调用优化TCO从而解决我们所说的普通递归的两大痛点编译器识别到尾递归时会做一个特殊优化当函数执行到尾递归这一步时它知道当前函数的栈帧已经没用了之后不会再用到任何局部变量也不需要回到当前函数继续执行于是编译器会直接销毁当前栈帧用同一个栈帧去执行下一次函数调用结果就是递归深度再深也只占用1个栈帧永远不会栈溢出这里我们提供一下.c代码#define_CRT_SECURE_NO_WARNINGS#includestdio.h//斐波那契数列intFibTail(intnum,inta,intb){if(num1){returna;}else{returnFibTail(num-1,b,ab);}}intFib(intnum){if(num1)return0;returnfibTail(num,1,1);}intmain(){intnum0;scanf(%d,num);intresultFib(num);printf(第%d项为%d\n,num,result);return0;}我们来看尾递归的参数a和b 它们在干什么a保存的是第一项 b保存的是第二项a b直接算出第三项作为下一次函数调用的b也就是说尾递归把原来的“树形拆分”改成了“线性递推”每一层递归只干一件事用前两项算下一项再把这两个数往下传没有任何回溯过程没有任何重复计算运行速度基本和迭代持平当然也需要注意尾递归的这些功能必须依赖编译器的尾调用优化TCOGCC / Clang编译器开启 -O2 优化后尾递归会被优化成循环栈不增长不溢出而VS的MSVC编译器是默认不支持尾调用优化的写了尾递归也不会被优化和普通递归一样会栈溢出运行速度慢所以在使用尾递归的时候也需要明确自己的编译器是不是支持尾调用优化的