递归复习总结学到指针后回头看从基础吃透递归学到指针后回头复习递归初学留下的诸多困惑竟慢慢通透。递归作为编程基础且易绕晕的知识点是后续学习的基石也是新手入门的 “小难关”—— 初学时常陷入 “栈溢出”“逻辑绕圈”“不知如何终止” 的误区对着简单阶乘代码也需反复琢磨如今掌握指针基础回头再看递归发现无需复杂内容也能将其学扎实。本文以 “回头复习” 的视角避开数据结构相关深层内容仅围绕基础知识点从定义、核心条件、执行过程、编写步骤到基础实战案例、避坑技巧层层拆解递归分享从 “模糊理解” 到 “扎实掌握” 的复习过程帮和我一样学到指针后回头复习递归的小伙伴少走弯路、吃透基础。一、什么是递归回头看才懂的核心逻辑初学总被 “函数自己调用自己” 的表面定义困住直到学到指针、回头复习才真正抓住递归的核心 ——核心不是 “自调用”而是 “分治思想 调用栈机制”。简单来说把一个复杂的大问题拆解成和原问题结构相同、但规模更小的子问题一直拆解到子问题简单到可以直接解决终止条件再通过子问题的解反向推导原问题的解。用两个通俗比喻理解递归查字典查陌生词可能需要先查关联词直到查到熟悉的基础词再回头理解原词俄罗斯套娃从最外层大娃一层一层拆到最小娃再一层一层套回去才算完成整个过程。结合指针的学习经验补充递归和指针一样都是 “化繁为简” 的思路指针通过地址直接操作数据、简化代码递归通过拆解问题、简化复杂逻辑两者虽不直接相关但核心思路相通。递归的核心定义自己调用自己拆解问题、回溯求解底层依赖函数调用栈的先进后出机制。二、递归的两个 “硬性条件”缺一不可踩过坑才懂初学写递归函数时常犯 “忘记终止条件” 或 “递推关系错误” 的问题导致程序无限递归、栈溢出调试半天找不到问题。所有正确的递归函数都必须满足两个缺一不可的硬性条件这是新手入门和回头复习都要牢记的基础。1. 终止条件Base Case递归的 “出口”也是现在写递归函数最先考虑的部分。指当子问题的规模缩小到一定程度不需要再递归调用自身就能直接返回结果的条件。比如求阶乘时n1 时无需调用 f (n-1)直接返回 1 即可这就是终止条件。核心坑点 注意终止条件必须可达到若递推过程中永远触达不到终止条件会陷入无限递归最终导致栈溢出 —— 这和写指针代码时忘记判断指针为空NULL的隐患相似都是 “没留出口” 的问题。2. 递推关系Recursive Case“如何拆解问题” 的核心是连接原问题和子问题的桥梁 —— 将原问题拆解为一个或多个规模更小、结构与原问题一致的子问题且子问题的解能通过一定逻辑推导得出原问题的解。核心要求每次递归调用问题的规模必须严格缩小。比如求阶乘时f(n) n * f(n-1)将 f (n) 拆解为 f (n-1)规模从 n 缩小到 n-1求 1~n 的和时f(n) n f(n-1)规模也在不断缩小。若问题规模未缩小如f(n) f(n)会陷入无限递归和指针操作中的 “死循环” 问题类似。三、递归的执行过程“递下去归回来”亲手调试才懂初学误以为递归是 “同时执行多个函数调用”这次回头复习通过 IDE 断点调试、手动模拟调用栈变化彻底搞懂其本质 ——递归的执行过程是 “递下去归回来” 的两步走底层是迭代循环的一种封装依赖函数调用栈的压入和弹出无需复杂概念记住这两步即可。1. 递向下拆解调用递归函数时函数会不断调用自身将大问题拆成小问题此过程为 “递”。关键特点“递” 的过程中函数不返回任何结果仅将每次的函数调用信息入参、局部变量等压入函数调用栈直到触达终止条件“递” 才停止。2. 归向上回溯触达终止条件后函数开始返回结果此过程为 “归”。执行逻辑从终止条件对应的子问题开始依次将结果返回给上层调用函数上层函数利用子问题的结果计算自身结果再继续向上返回直到回到最开始的原问题调用完成整个计算。此过程中函数调用栈会依次弹出之前压入的函数信息。3.复习感悟最初理解这一步时始终绕晕这次用求 n 的阶乘手动模拟调用栈的压入和弹出瞬间通透。示例求 f (3)调用 f (3)压入栈f (3) 调用 f (2)压入栈f (2) 调用 f (1)压入栈f (1) 触达终止条件返回 1弹出栈f (2) 拿到结果计算 2*12返回 2弹出栈f (3) 拿到结果计算 3*26返回 6弹出栈计算完成。核心总结递归的执行一定是 “先递后归”没有例外。看不懂时手动模拟调用栈或用 IDE 断点调试比死记硬背更有用 —— 这和调试指针代码时一步步查看地址变化是同一个道理。四、如何编写递归函数我的四步走万能模板摆脱 “凭感觉写递归” 后总结出适用于所有基础递归场景的四步走编写流程无需复杂内容无论是简单阶乘还是结合指针的基础递归按步骤写都能从 “会写” 到 “写对”。1. 明确函数的功能先 “知其能”再 “写其体”最容易被新手忽略的一步写代码前先想清楚递归函数要解决什么问题入参是什么需要传入哪些数据返回值是什么要返回什么结果关键不要一开始纠结函数内部的递归调用先明确 “这个函数能做什么”。示例求阶乘入参是整数 n返回值是 n 的阶乘功能是计算 n 的阶乘指针版数组求和入参是数组指针和数组长度返回值是数组元素和功能是计算数组所有元素的和。2. 找出终止条件先写 “出口”再写 “路径”结合踩坑经验写递归函数一定要先写终止条件再写递推关系。思考当入参满足什么条件时不需要再递归能直接返回结果验证要点终止条件是否可达到是否能覆盖所有极端情况如 n0、指针为空—— 就像写指针代码时一定要先判断指针是否为空避免越界。3. 推导递推关系拆解问题连接子问题与原问题递归的核心步骤考验逻辑思维但基础场景下非常简单。思考如何将原问题拆解为一个或多个规模更小、结构一致的子问题子问题的解如何通过逻辑计算得到原问题的解4. 验证逻辑闭环用小案例测试避免踩坑写完代码后不直接运行先用小案例手动测试验证逻辑是否正确。示例阶乘函数测试 n1、n2、n3指针版数组求和测试长度为 1、2 的数组。避免出现指针越界、递归逻辑错误等问题。结合指针的基础递归模板以数组求和为例// 结合指针的数组求和递归函数 int sum_array(int *arr, int len) { // 步骤2终止条件指针为空/数组长度为0返回0 if (len 0 || arr NULL) { return 0; } // 步骤3递推关系指针后移arr1数组长度减1规模缩小 int sub_result sum_array(arr 1, len - 1); // 利用子问题结果计算原问题结果当前元素 剩余元素和 int result *arr sub_result; // 返回结果 return result; }五、基础递归实战案例递归的掌握离不开基础实战本次复习整理5 个最基础的案例附思路分析和代码实现跟着练就能扎实掌握。案例 1阶乘计算f (n) n!5.1.1 阶乘定义对于非负整数 nn 的阶乘记为 n!数学定义基础定义n! n × (n-1) × (n-2) × … × 2 × 1n≥1特殊规定0! 1标准化定义满足排列组合、级数展开等公式的一致性。示例1! 1、3! 6、5! 120、7! 5040拆解逻辑n! n×(n-1)!、(n-1)! (n-1)×(n-2)!…… 最终到 1! 1。5.1.2 解题思路明确功能接收整数 n返回 n 的阶乘终止条件n1 或 n0 时返回 1覆盖 0! 的数学定义避免 n0 时无限递归递推关系f (n) n × f (n-1)将求 n 的阶乘拆解为求 n-1 的阶乘规模缩小验证测试 n3得到 6验证正确。5.1.3 C 语言代码#include stdio.h // 阶乘递归函数修正补充n0的终止条件符合数学定义 int factorial(int n) { // 终止条件覆盖0!和1!避免n0时无限递归 if (n 0 || n 1) { return 1; } // 递推关系简化写法符合四步流程 return n * factorial(n - 1); } int main() { int n 5; printf(%d的阶乘是%d\n, n, factorial(n)); // 输出120 return 0; }画图演示案例 2求 1~n 的和f (n) n f (n-1)5.2.1 解题思路明确功能接收整数 n返回 1 到 n 的累加和终止条件n1 时返回 11 的和就是自身递推关系f (n) n f (n-1)拆解为 “n 1~n-1 的和”验证测试 n51234515验证正确。5.2.2 C 语言代码#include stdio.h // 1~n求和递归函数 int sum_1_to_n(int n) { // 终止条件 if (n 1) { return 1; } // 递推关系 return n sum_1_to_n(n - 1); } int main() { int n 5; printf(1~%d的和是%d\n, n, sum_1_to_n(n)); // 输出15 return 0; }案例 3结合指针求数组元素的和结合刚学的指针难度与前两个一致既能巩固递归又能复习指针基础用法非常适合回头复习。5.3.1 解题思路明确功能接收数组指针 arr 和数组长度 len返回数组所有元素的和终止条件len0无元素或 arrNULL指针为空返回 0递推关系当前指针指向的元素*arr 剩余数组arr1len-1的和规模逐步缩小验证数组 {1,2,3}和为 6验证正确。5.3.2 C 语言代码#include stdio.h // 结合指针的数组求和递归函数 int sum_array(int *arr, int len) { // 终止条件指针为空或长度为0返回0 if (arr NULL || len 0) { return 0; } // 递推关系当前元素 剩余元素和指针后移长度减1 return *arr sum_array(arr 1, len - 1); } int main() { int arr[] {1, 2, 3, 4, 5}; int len sizeof(arr) / sizeof(arr[0]); // 计算数组实际长度 printf(数组元素的和是%d\n, sum_array(arr, len)); // 输出15 return 0; }案例 4顺序打印一个整数的每一位常规取余 / 除法会得到倒序结果利用递归 “先递后归” 的特性可直接实现顺序打印重点理解递归的执行顺序。5.4.1 解题思路明确功能接收整数 n按从高位到低位的顺序打印每一位终止条件n ≤ 9只有一位数直接打印递推关系先递归打印 n/10 的每一位再打印 n%10最后一位验证测试 n123打印 1 2 3验证正确。5.42 C 语言代码#include stdio.h // 顺序打印整数的每一位处理正整数负数可先取绝对值 void print_num(int n) { // 终止条件只有一位数直接打印 if (n 9) { print_num(n / 10); // 递去掉最后一位继续递归 } // 归打印当前最后一位 printf(%d , n % 10); } int main() { int n; printf(请输入一个整数); scanf(%d, n); // 处理负数先打印负号再取绝对值打印 if (n 0) { printf(-); n -n; } print_num(n); // 示例输入123输出1 2 3 return 0; }案例 5求第 n 个斐波那契数斐波那契数是经典递推数列重点体会递归的重复计算隐患为后续避坑和优化做铺垫。5.5.1 定义与表示斐波那契数列记为 {Fn}下标从 0 开始是数学和编程的通用标准基础项初始条件F00F11递推项核心规律FnFn−1Fn−2 (n≥2)。5.5.2 解题思路递归版明确功能接收非负整数 n返回第 n 个斐波那契数终止条件n0 返回 0n1 返回 1递推关系Fn Fn-1 Fn-2n≥2验证测试 n5F55验证正确。5.5.3 递归版 C 语言代码#define _CRT_SECURE_NO_WARNINGS #include stdio.h // 斐波那契数递归函数 long long Fib(int n) { // 终止条件覆盖基础项F0、F1 if (n 0) { return 0; } else if (n 1) { return 1; } else { // 递推关系存在大量重复计算 return Fib(n - 1) Fib(n - 2); } } int main() { int n; printf(请输入非负整数n); scanf(%d, n); if (n 0) { printf(错误请输入非负整数\n); return 1; } long long num Fib(n); printf(第%d个斐波那契数为%lld\n, n, num); return 0; }5.5.4递归的重复计算问题验证通过全局变量统计第 3 个斐波那契数的计算次数会发现 n 越大重复计算次数呈指数级增长如 n30 时F3 被计算 317811 次。#define _CRT_SECURE_NO_WARNINGS #include stdio.h int count 0; // 全局变量统计第3个斐波那契数被计算的次数 long long Fib(int n) { if (n 3) { count; // 统计F3的计算次数 } else if (n 0) { return 0; } else if (n 1) { return 1; } else { return Fib(n - 1) Fib(n - 2); } } int main() { int n; scanf(%d, n); if (n 0) { printf(错误请输入非负整数\n); return 1; } long long num Fib(n); printf(第%d个斐波那契数为%lld\n,n, num); printf(第3个斐波那契数被计算的次数%d\n, count); return 0; }5.5.5 优化迭代版斐波那契避免重复计算递归版斐波那契因重复计算效率极低基础阶段优先用迭代循环实现思路更简单且无冗余计算。#define _CRT_SECURE_NO_WARNINGS #include stdio.h // 斐波那契数迭代版无重复计算效率高 long long Fib_iter(int n) { // 终止条件覆盖F0、F1 if (n 0) return 0; if (n 1) return 1; // 迭代计算用变量保存前两项逐步推导 long long a 0; // F0 long long b 1; // F1 long long c 0; // 保存当前项 for (int i 2; i n; i) { c a b; a b; b c; } return c; } int main() { int n; printf(请输入非负整数n); scanf(%d, n); if (n 0) { printf(错误请输入非负整数\n); return 1; } long long num Fib_iter(n); printf(第%d个斐波那契数为%lld\n, n, num); return 0; }六、递归的常见坑与避坑技巧复习时重点规避6.1 坑 1忘记写终止条件 / 终止条件错误表现程序无限递归最终栈溢出、报错终止如阶乘函数忘记写 n1 返回 1会一直调用 f (n-1) 直到崩溃避坑技巧写递归函数第一步永远是写终止条件写完后用小案例验证确保终止条件可达到且覆盖所有极端情况如 n0、指针为空。6.2 坑 2问题规模未严格缩小表现虽写了终止条件但递推关系中问题规模未缩小如f(n) f(n)、f(n) f(n1)导致永远触达不到终止条件陷入无限递归避坑技巧写完递推关系后检查每次递归的入参是否比原入参 “更小”如 n→n-1、len→len-1确保规模朝着终止条件靠近。6.3 坑 3栈溢出Stack Overflow表现递归深度过大时超出编程语言的调用栈限制函数调用栈无法承载过多栈帧如 C 语言测试阶乘 n1000 时会栈溢出原因递归的 “天生隐患”底层依赖函数调用栈栈的内存空间有限避坑技巧基础复习阶段控制递归深度在 1000 以内C/Python 默认递归深度约 1000不用过度纠结复杂优化后续深入学习后再考虑栈优化、尾递归等方式。6.4 坑 4重复计算如斐波那契数列表现存在大量重复子问题的递归场景运行速度极慢如斐波那契 n30 时递归版明显卡顿迭代版瞬间出结果避坑技巧基础阶段暂时避开这类案例重点练习阶乘、数组求和等无重复子问题的递归若要练习记住 “用变量缓存子问题结果” 即可不用深入。七、递归的优化手段基础阶段掌握简单优化即可基础阶段的递归不用追求复杂优化掌握最基础、最实用的优化手段就够了重点是 “能写对、能运行”后续深入学习后再补充复杂优化。1. 简单缓存优化避免重复计算针对存在重复子问题的递归如斐波那契用变量 / 数组缓存已经计算过的子问题结果下次调用时直接使用缓存值避免重复计算。基础实现用全局数组缓存斐波那契数适合新手理解。2. 避免深层递归防止栈溢出基础阶段最直接的优化方式控制递归深度若需要计算更大的数值如 n10000直接改用迭代循环实现无需研究复杂的栈优化 / 尾递归。3. 优先用迭代替代若一个问题存在大量重复子问题如斐波那契、青蛙跳台阶或需要极深的递归深度直接用迭代实现—— 递归的优势是代码简洁而非效率基础阶段要理性选择。八、递归的适用场景与局限性基础阶段理性使用练熟基础递归后容易陷入 “凡事都用递归” 的误区但递归并非万能基础阶段要学会 “理性使用”明确其适用场景和局限性。8.1 适用场景基础阶段重点关注 2 个问题可拆解为规模更小、结构相同的子问题如阶乘、1~n 的和、数组求和这类问题的递归代码比循环更简洁、更易理解练习逻辑思维巩固函数调用机制结合指针写递归如数组求和、数组遍历既能复习递归又能加深对指针的理解为后续学习打基础。8.2 局限性基础阶段重点规避栈溢出风险递归深度过大时超出调用栈限制导致程序崩溃部分场景效率低未优化的递归在存在大量重复子问题的场景下存在严重的重复计算运行速度极慢调试难度稍高相比循环递归的执行过程更抽象新手调试时需手动模拟调用栈或断点调试。8.3 核心使用原则基础阶段不用追求 “用递归解决所有问题”核心原则简单问题、可拆解的问题用递归练手深层递归、重复子问题多的问题暂时用迭代替代重点是 “吃透基础、巩固思路”而非盲目追求复杂用法。九、递归思想的延伸基础阶段不用太深递归并非孤立知识点是后续学习复杂算法的基础但基础阶段只需知道其和当前 / 后续知识点的简单关联避免增加学习负担。1. 递归与指针核心思路相通两者的核心都是化繁为简指针通过地址直接操作数据简化代码书写和内存操作递归通过拆解问题为子问题简化复杂的逻辑实现。实战结合多写 “指针 递归” 的简单案例如数组求和、数组遍历一举两得融会贯通。2. 递归与循环递归是循环的封装递归的底层是迭代循环的一种封装依赖函数调用栈实现 “循环调用自身”。基础练习尝试将简单的递归转循环如阶乘、1~n 的和加深对两者的理解 —— 所有简单的递归都能改成循环实现。3. 递归与后续学习打基础的核心知识点递归是后续学习数据结构和算法的基础如数据结构二叉树的遍历前序 / 中序 / 后序、链表的反转算法分治算法、回溯算法、深度优先搜索DFS。基础阶段吃透递归后续学习这些内容会事半功倍。十、复习总结与学习建议写给和我一样回头复习的小伙伴学到指针后回头复习递归最大的感悟是递归不用追求 “学得多深”基础阶段吃透定义、核心条件、编写步骤和基础案例避开常见坑就足够了很多之前的困惑会随着后续学习如指针、数据结构的深入慢慢通透。1.核心知识点回顾递归的本质是分治思想 函数调用栈核心要求是终止条件 递推关系执行过程必然是 “先递后归”没有例外编写递归的万能步骤明功能→找终止→推递推→验逻辑一定要先写终止条件再写递推关系基础阶段重点练习阶乘、数组求和结合指针等无重复子问题的递归控制递归深度避开斐波那契这类天生不适合递归的场景。2.适合回头复习的学习建议结合 “学到指针后回头复习” 的经历给小伙伴 3 个实用建议坚持做就能扎实掌握递归基础从最简单的案例入手反复练不要一开始挑战复杂案例重点练阶乘、1~n 的和、指针 数组求和、顺序打印整数这 4 个案例每个案例写 2~3 遍手动模拟执行过程加深理解严格按步骤写代码养成习惯不要凭感觉写递归严格遵循 “四步走” 流程先明确功能再写终止条件接着推导递推关系最后验证避免踩坑结合指针融会贯通多写 “指针 递归” 的简单案例如数组求和、数组遍历、指针版逆序打印字符串既能巩固递归又能复习指针的地址操作、指针移动等基础用法。十一、拓展学习拓展 1青蛙跳台阶问题基础版11.1.1 问题描述一只青蛙要跳上 n 级台阶每次只能跳 1 级或 2 级台阶问跳上 n 级台阶一共有多少种不同的跳法11.1.2 解题思路从「最后一步」反向分析推导出斐波那契递推公式设跳上 n 级台阶有 f (n) 种跳法最后一步只有两种可能跳 1 级前面需跳 n-1 级f (n-1) 种、跳 2 级前面需跳 n-2 级f (n-2) 种总跳法f (n) f (n-1) f (n-2)终止条件n1 时 f (1)1n2 时 f (2)2。11.1.3 C 语言代码#include stdio.h // 青蛙跳台阶递归版基础版存在重复计算n不宜过大 long long jump_step(int n) { if (n 1) { return 1; } else if (n 2) { return 2; } else { return jump_step(n - 1) jump_step(n - 2); } } int main() { int n; printf(请输入台阶数正整数); scanf(%d, n); if (n 1) { printf(错误台阶数需为正整数\n); return 1; } long long num jump_step(n); printf(跳上%d级台阶共有%lld种跳法\n, n, num); return 0; }十二、补充汉诺塔Hanoi Tower问题详解汉诺塔是递归算法的经典问题由法国数学家爱德华・卢卡斯提出核心是通过有限次移动规则将一堆盘子从一个柱子移到另一个柱子解题关键是把复杂问题拆解为规模更小的同类型问题 —— 完美契合递归的分治思想。1.汉诺塔问题描述与核心规则1.1 问题描述有 3 根柱子通常记为 A、B、C和 n 个大小不同的圆盘初始时所有圆盘从小到大叠在 A 柱大的在底部小的在顶部要求将所有圆盘全部移到 C 柱最终叠放顺序和初始一致大下小上。1.2 核心移动规则每次只能移动 1 个圆盘移动过程中任何时刻都不能出现「大圆盘压在小圆盘上」的情况3 根柱子都可作为临时存放圆盘的中间载体如 B 柱常作为 A→C 的中转。1.3 直观示例n3 个圆盘最易理解的基础案例最终需要7 次移动完成能直观看到递归的拆解过程把 A 柱最上面的小圆盘移到 C 柱把 A 柱中间的圆盘移到 B 柱把 C 柱的小圆盘移到 B 柱把 A 柱最大的圆盘移到 C 柱把 B 柱的小圆盘移到 A 柱把 B 柱中间的圆盘移到 C 柱把 A 柱的小圆盘移到 C 柱。2.核心解题思路递归分治最关键汉诺塔的递归思想核心是 「大事化小」—— 要移动 n 个圆盘先解决 n-1 个圆盘的移动问题无论 n 多大拆解步骤只有 3 步这是递归能实现的根本原因。2.1 递归拆解公式记为Hanoi(n, A, B, C)表示n 个盘从源柱 A经中转柱 B移到目标柱 C。第一步把 A 柱上最上面的 n-1 个圆盘经 C 柱中转移到 B 柱 →Hanoi(n-1, A, C, B)暴露最大的圆盘才能单独移动第二步把 A 柱上剩下的 1 个最大圆盘直接移到 C 柱唯一一次移动最大盘递归终止条件的铺垫第三步把 B 柱上暂存的 n-1 个圆盘经 A 柱中转移到 C 柱 →Hanoi(n-1, B, A, C)把小圆盘移到目标柱叠在最大盘上。2.2 递归终止条件当 n1 时只有 1 个圆盘无需中转直接将圆盘从源柱移到目标柱即可 —— 这是递归的「出口」避免无限调用。2.3 核心规律移动 n 个汉诺塔圆盘最少需要 2ⁿ−1 次移动n1 时 1 次n2 时 3 次n3 时 7 次n4 时 15 次符合规律递归的核心是关注「当前要做什么」而非「每一步具体怎么移」不用纠结 n10 时的每一步移动细节只需明确 3 步拆解逻辑计算机会自动处理 n-1、n-2… 的子问题。3.汉诺塔 C 语言代码实现#define _CRT_SECURE_NO_WARNINGS #include stdio.h // 汉诺塔递归函数 // n要移动的圆盘数量 // from源柱子初始A字符表示 // mid中转柱子初始B // to目标柱子初始C void Hanoi(int n, char from, char mid, char to) { // 递归终止条件n1直接从源柱移到目标柱输出移动步骤 if (n 1) { printf(将第%d个圆盘从%c柱移到%c柱\n, n, from, to); return; } // 第一步n-1个盘从from经to中转移到mid Hanoi(n - 1, from, to, mid); // 第二步第n个盘最大的直接从from移到to输出步骤 printf(将第%d个圆盘从%c柱移到%c柱\n, n, from, to); // 第三步n-1个盘从mid经from中转移到to Hanoi(n - 1, mid, from, to); } int main() { int n; printf(请输入汉诺塔的圆盘数量); scanf(%d, n); // 输入合法性判断圆盘数必须是正整数 if (n 1) { printf(错误圆盘数量需为正整数\n); return 1; } // 调用汉诺塔函数n个盘从A经B中转移到C Hanoi(n, A, B, C); // 输出最少移动次数1LLn 避免整数溢出等价于2^n printf(完成%d个圆盘的汉诺塔最少需要%lld次移动\n, n, (1LL n) - 1); return 0; }十三、结尾其实递归的基础学习真的不用太焦虑。我刚开始学习时也经常绕圈、踩坑甚至怀疑自己是不是学不会但学到指针后回头复习才发现很多困惑都迎刃而解了。最后想和大家互动一下你在学到指针后回头复习递归有没有发现哪些之前不懂的地方现在突然通透了或者在练习 “指针 递归” 的案例时遇到了哪些小问题欢迎在评论区留言交流我们一起探讨、一起进步。如果这篇复习总结对你有帮助也欢迎点赞、收藏你的支持就是我继续分享的动力十四、附录基础知识点补充供复习参考1. 常见编程语言的递归深度限制C 语言默认约 1000、Python 默认约 1000、Java 默认约 10000基础阶段控制递归深度在 1000 以内即可避免栈溢出。2. 基础递归转循环示例阶乘以阶乘为例递归转循环的思路简单基础阶段可多尝试加深对递归和循环的理解。// 阶乘递归转循环迭代版 int factorial_loop(int n) { int result 1; for (int i 1; i n; i) { result * i; } return result; }3. 指针基础补充在 “指针 递归” 的案例中arr1表示数组指针向后移动一位指向数组的下一个元素等价于arr[1]是指针的基础用法也是递归中 “缩小问题规模” 的关键。
吃透递归的底层逻辑：我的回头重学实战总结
递归复习总结学到指针后回头看从基础吃透递归学到指针后回头复习递归初学留下的诸多困惑竟慢慢通透。递归作为编程基础且易绕晕的知识点是后续学习的基石也是新手入门的 “小难关”—— 初学时常陷入 “栈溢出”“逻辑绕圈”“不知如何终止” 的误区对着简单阶乘代码也需反复琢磨如今掌握指针基础回头再看递归发现无需复杂内容也能将其学扎实。本文以 “回头复习” 的视角避开数据结构相关深层内容仅围绕基础知识点从定义、核心条件、执行过程、编写步骤到基础实战案例、避坑技巧层层拆解递归分享从 “模糊理解” 到 “扎实掌握” 的复习过程帮和我一样学到指针后回头复习递归的小伙伴少走弯路、吃透基础。一、什么是递归回头看才懂的核心逻辑初学总被 “函数自己调用自己” 的表面定义困住直到学到指针、回头复习才真正抓住递归的核心 ——核心不是 “自调用”而是 “分治思想 调用栈机制”。简单来说把一个复杂的大问题拆解成和原问题结构相同、但规模更小的子问题一直拆解到子问题简单到可以直接解决终止条件再通过子问题的解反向推导原问题的解。用两个通俗比喻理解递归查字典查陌生词可能需要先查关联词直到查到熟悉的基础词再回头理解原词俄罗斯套娃从最外层大娃一层一层拆到最小娃再一层一层套回去才算完成整个过程。结合指针的学习经验补充递归和指针一样都是 “化繁为简” 的思路指针通过地址直接操作数据、简化代码递归通过拆解问题、简化复杂逻辑两者虽不直接相关但核心思路相通。递归的核心定义自己调用自己拆解问题、回溯求解底层依赖函数调用栈的先进后出机制。二、递归的两个 “硬性条件”缺一不可踩过坑才懂初学写递归函数时常犯 “忘记终止条件” 或 “递推关系错误” 的问题导致程序无限递归、栈溢出调试半天找不到问题。所有正确的递归函数都必须满足两个缺一不可的硬性条件这是新手入门和回头复习都要牢记的基础。1. 终止条件Base Case递归的 “出口”也是现在写递归函数最先考虑的部分。指当子问题的规模缩小到一定程度不需要再递归调用自身就能直接返回结果的条件。比如求阶乘时n1 时无需调用 f (n-1)直接返回 1 即可这就是终止条件。核心坑点 注意终止条件必须可达到若递推过程中永远触达不到终止条件会陷入无限递归最终导致栈溢出 —— 这和写指针代码时忘记判断指针为空NULL的隐患相似都是 “没留出口” 的问题。2. 递推关系Recursive Case“如何拆解问题” 的核心是连接原问题和子问题的桥梁 —— 将原问题拆解为一个或多个规模更小、结构与原问题一致的子问题且子问题的解能通过一定逻辑推导得出原问题的解。核心要求每次递归调用问题的规模必须严格缩小。比如求阶乘时f(n) n * f(n-1)将 f (n) 拆解为 f (n-1)规模从 n 缩小到 n-1求 1~n 的和时f(n) n f(n-1)规模也在不断缩小。若问题规模未缩小如f(n) f(n)会陷入无限递归和指针操作中的 “死循环” 问题类似。三、递归的执行过程“递下去归回来”亲手调试才懂初学误以为递归是 “同时执行多个函数调用”这次回头复习通过 IDE 断点调试、手动模拟调用栈变化彻底搞懂其本质 ——递归的执行过程是 “递下去归回来” 的两步走底层是迭代循环的一种封装依赖函数调用栈的压入和弹出无需复杂概念记住这两步即可。1. 递向下拆解调用递归函数时函数会不断调用自身将大问题拆成小问题此过程为 “递”。关键特点“递” 的过程中函数不返回任何结果仅将每次的函数调用信息入参、局部变量等压入函数调用栈直到触达终止条件“递” 才停止。2. 归向上回溯触达终止条件后函数开始返回结果此过程为 “归”。执行逻辑从终止条件对应的子问题开始依次将结果返回给上层调用函数上层函数利用子问题的结果计算自身结果再继续向上返回直到回到最开始的原问题调用完成整个计算。此过程中函数调用栈会依次弹出之前压入的函数信息。3.复习感悟最初理解这一步时始终绕晕这次用求 n 的阶乘手动模拟调用栈的压入和弹出瞬间通透。示例求 f (3)调用 f (3)压入栈f (3) 调用 f (2)压入栈f (2) 调用 f (1)压入栈f (1) 触达终止条件返回 1弹出栈f (2) 拿到结果计算 2*12返回 2弹出栈f (3) 拿到结果计算 3*26返回 6弹出栈计算完成。核心总结递归的执行一定是 “先递后归”没有例外。看不懂时手动模拟调用栈或用 IDE 断点调试比死记硬背更有用 —— 这和调试指针代码时一步步查看地址变化是同一个道理。四、如何编写递归函数我的四步走万能模板摆脱 “凭感觉写递归” 后总结出适用于所有基础递归场景的四步走编写流程无需复杂内容无论是简单阶乘还是结合指针的基础递归按步骤写都能从 “会写” 到 “写对”。1. 明确函数的功能先 “知其能”再 “写其体”最容易被新手忽略的一步写代码前先想清楚递归函数要解决什么问题入参是什么需要传入哪些数据返回值是什么要返回什么结果关键不要一开始纠结函数内部的递归调用先明确 “这个函数能做什么”。示例求阶乘入参是整数 n返回值是 n 的阶乘功能是计算 n 的阶乘指针版数组求和入参是数组指针和数组长度返回值是数组元素和功能是计算数组所有元素的和。2. 找出终止条件先写 “出口”再写 “路径”结合踩坑经验写递归函数一定要先写终止条件再写递推关系。思考当入参满足什么条件时不需要再递归能直接返回结果验证要点终止条件是否可达到是否能覆盖所有极端情况如 n0、指针为空—— 就像写指针代码时一定要先判断指针是否为空避免越界。3. 推导递推关系拆解问题连接子问题与原问题递归的核心步骤考验逻辑思维但基础场景下非常简单。思考如何将原问题拆解为一个或多个规模更小、结构一致的子问题子问题的解如何通过逻辑计算得到原问题的解4. 验证逻辑闭环用小案例测试避免踩坑写完代码后不直接运行先用小案例手动测试验证逻辑是否正确。示例阶乘函数测试 n1、n2、n3指针版数组求和测试长度为 1、2 的数组。避免出现指针越界、递归逻辑错误等问题。结合指针的基础递归模板以数组求和为例// 结合指针的数组求和递归函数 int sum_array(int *arr, int len) { // 步骤2终止条件指针为空/数组长度为0返回0 if (len 0 || arr NULL) { return 0; } // 步骤3递推关系指针后移arr1数组长度减1规模缩小 int sub_result sum_array(arr 1, len - 1); // 利用子问题结果计算原问题结果当前元素 剩余元素和 int result *arr sub_result; // 返回结果 return result; }五、基础递归实战案例递归的掌握离不开基础实战本次复习整理5 个最基础的案例附思路分析和代码实现跟着练就能扎实掌握。案例 1阶乘计算f (n) n!5.1.1 阶乘定义对于非负整数 nn 的阶乘记为 n!数学定义基础定义n! n × (n-1) × (n-2) × … × 2 × 1n≥1特殊规定0! 1标准化定义满足排列组合、级数展开等公式的一致性。示例1! 1、3! 6、5! 120、7! 5040拆解逻辑n! n×(n-1)!、(n-1)! (n-1)×(n-2)!…… 最终到 1! 1。5.1.2 解题思路明确功能接收整数 n返回 n 的阶乘终止条件n1 或 n0 时返回 1覆盖 0! 的数学定义避免 n0 时无限递归递推关系f (n) n × f (n-1)将求 n 的阶乘拆解为求 n-1 的阶乘规模缩小验证测试 n3得到 6验证正确。5.1.3 C 语言代码#include stdio.h // 阶乘递归函数修正补充n0的终止条件符合数学定义 int factorial(int n) { // 终止条件覆盖0!和1!避免n0时无限递归 if (n 0 || n 1) { return 1; } // 递推关系简化写法符合四步流程 return n * factorial(n - 1); } int main() { int n 5; printf(%d的阶乘是%d\n, n, factorial(n)); // 输出120 return 0; }画图演示案例 2求 1~n 的和f (n) n f (n-1)5.2.1 解题思路明确功能接收整数 n返回 1 到 n 的累加和终止条件n1 时返回 11 的和就是自身递推关系f (n) n f (n-1)拆解为 “n 1~n-1 的和”验证测试 n51234515验证正确。5.2.2 C 语言代码#include stdio.h // 1~n求和递归函数 int sum_1_to_n(int n) { // 终止条件 if (n 1) { return 1; } // 递推关系 return n sum_1_to_n(n - 1); } int main() { int n 5; printf(1~%d的和是%d\n, n, sum_1_to_n(n)); // 输出15 return 0; }案例 3结合指针求数组元素的和结合刚学的指针难度与前两个一致既能巩固递归又能复习指针基础用法非常适合回头复习。5.3.1 解题思路明确功能接收数组指针 arr 和数组长度 len返回数组所有元素的和终止条件len0无元素或 arrNULL指针为空返回 0递推关系当前指针指向的元素*arr 剩余数组arr1len-1的和规模逐步缩小验证数组 {1,2,3}和为 6验证正确。5.3.2 C 语言代码#include stdio.h // 结合指针的数组求和递归函数 int sum_array(int *arr, int len) { // 终止条件指针为空或长度为0返回0 if (arr NULL || len 0) { return 0; } // 递推关系当前元素 剩余元素和指针后移长度减1 return *arr sum_array(arr 1, len - 1); } int main() { int arr[] {1, 2, 3, 4, 5}; int len sizeof(arr) / sizeof(arr[0]); // 计算数组实际长度 printf(数组元素的和是%d\n, sum_array(arr, len)); // 输出15 return 0; }案例 4顺序打印一个整数的每一位常规取余 / 除法会得到倒序结果利用递归 “先递后归” 的特性可直接实现顺序打印重点理解递归的执行顺序。5.4.1 解题思路明确功能接收整数 n按从高位到低位的顺序打印每一位终止条件n ≤ 9只有一位数直接打印递推关系先递归打印 n/10 的每一位再打印 n%10最后一位验证测试 n123打印 1 2 3验证正确。5.42 C 语言代码#include stdio.h // 顺序打印整数的每一位处理正整数负数可先取绝对值 void print_num(int n) { // 终止条件只有一位数直接打印 if (n 9) { print_num(n / 10); // 递去掉最后一位继续递归 } // 归打印当前最后一位 printf(%d , n % 10); } int main() { int n; printf(请输入一个整数); scanf(%d, n); // 处理负数先打印负号再取绝对值打印 if (n 0) { printf(-); n -n; } print_num(n); // 示例输入123输出1 2 3 return 0; }案例 5求第 n 个斐波那契数斐波那契数是经典递推数列重点体会递归的重复计算隐患为后续避坑和优化做铺垫。5.5.1 定义与表示斐波那契数列记为 {Fn}下标从 0 开始是数学和编程的通用标准基础项初始条件F00F11递推项核心规律FnFn−1Fn−2 (n≥2)。5.5.2 解题思路递归版明确功能接收非负整数 n返回第 n 个斐波那契数终止条件n0 返回 0n1 返回 1递推关系Fn Fn-1 Fn-2n≥2验证测试 n5F55验证正确。5.5.3 递归版 C 语言代码#define _CRT_SECURE_NO_WARNINGS #include stdio.h // 斐波那契数递归函数 long long Fib(int n) { // 终止条件覆盖基础项F0、F1 if (n 0) { return 0; } else if (n 1) { return 1; } else { // 递推关系存在大量重复计算 return Fib(n - 1) Fib(n - 2); } } int main() { int n; printf(请输入非负整数n); scanf(%d, n); if (n 0) { printf(错误请输入非负整数\n); return 1; } long long num Fib(n); printf(第%d个斐波那契数为%lld\n, n, num); return 0; }5.5.4递归的重复计算问题验证通过全局变量统计第 3 个斐波那契数的计算次数会发现 n 越大重复计算次数呈指数级增长如 n30 时F3 被计算 317811 次。#define _CRT_SECURE_NO_WARNINGS #include stdio.h int count 0; // 全局变量统计第3个斐波那契数被计算的次数 long long Fib(int n) { if (n 3) { count; // 统计F3的计算次数 } else if (n 0) { return 0; } else if (n 1) { return 1; } else { return Fib(n - 1) Fib(n - 2); } } int main() { int n; scanf(%d, n); if (n 0) { printf(错误请输入非负整数\n); return 1; } long long num Fib(n); printf(第%d个斐波那契数为%lld\n,n, num); printf(第3个斐波那契数被计算的次数%d\n, count); return 0; }5.5.5 优化迭代版斐波那契避免重复计算递归版斐波那契因重复计算效率极低基础阶段优先用迭代循环实现思路更简单且无冗余计算。#define _CRT_SECURE_NO_WARNINGS #include stdio.h // 斐波那契数迭代版无重复计算效率高 long long Fib_iter(int n) { // 终止条件覆盖F0、F1 if (n 0) return 0; if (n 1) return 1; // 迭代计算用变量保存前两项逐步推导 long long a 0; // F0 long long b 1; // F1 long long c 0; // 保存当前项 for (int i 2; i n; i) { c a b; a b; b c; } return c; } int main() { int n; printf(请输入非负整数n); scanf(%d, n); if (n 0) { printf(错误请输入非负整数\n); return 1; } long long num Fib_iter(n); printf(第%d个斐波那契数为%lld\n, n, num); return 0; }六、递归的常见坑与避坑技巧复习时重点规避6.1 坑 1忘记写终止条件 / 终止条件错误表现程序无限递归最终栈溢出、报错终止如阶乘函数忘记写 n1 返回 1会一直调用 f (n-1) 直到崩溃避坑技巧写递归函数第一步永远是写终止条件写完后用小案例验证确保终止条件可达到且覆盖所有极端情况如 n0、指针为空。6.2 坑 2问题规模未严格缩小表现虽写了终止条件但递推关系中问题规模未缩小如f(n) f(n)、f(n) f(n1)导致永远触达不到终止条件陷入无限递归避坑技巧写完递推关系后检查每次递归的入参是否比原入参 “更小”如 n→n-1、len→len-1确保规模朝着终止条件靠近。6.3 坑 3栈溢出Stack Overflow表现递归深度过大时超出编程语言的调用栈限制函数调用栈无法承载过多栈帧如 C 语言测试阶乘 n1000 时会栈溢出原因递归的 “天生隐患”底层依赖函数调用栈栈的内存空间有限避坑技巧基础复习阶段控制递归深度在 1000 以内C/Python 默认递归深度约 1000不用过度纠结复杂优化后续深入学习后再考虑栈优化、尾递归等方式。6.4 坑 4重复计算如斐波那契数列表现存在大量重复子问题的递归场景运行速度极慢如斐波那契 n30 时递归版明显卡顿迭代版瞬间出结果避坑技巧基础阶段暂时避开这类案例重点练习阶乘、数组求和等无重复子问题的递归若要练习记住 “用变量缓存子问题结果” 即可不用深入。七、递归的优化手段基础阶段掌握简单优化即可基础阶段的递归不用追求复杂优化掌握最基础、最实用的优化手段就够了重点是 “能写对、能运行”后续深入学习后再补充复杂优化。1. 简单缓存优化避免重复计算针对存在重复子问题的递归如斐波那契用变量 / 数组缓存已经计算过的子问题结果下次调用时直接使用缓存值避免重复计算。基础实现用全局数组缓存斐波那契数适合新手理解。2. 避免深层递归防止栈溢出基础阶段最直接的优化方式控制递归深度若需要计算更大的数值如 n10000直接改用迭代循环实现无需研究复杂的栈优化 / 尾递归。3. 优先用迭代替代若一个问题存在大量重复子问题如斐波那契、青蛙跳台阶或需要极深的递归深度直接用迭代实现—— 递归的优势是代码简洁而非效率基础阶段要理性选择。八、递归的适用场景与局限性基础阶段理性使用练熟基础递归后容易陷入 “凡事都用递归” 的误区但递归并非万能基础阶段要学会 “理性使用”明确其适用场景和局限性。8.1 适用场景基础阶段重点关注 2 个问题可拆解为规模更小、结构相同的子问题如阶乘、1~n 的和、数组求和这类问题的递归代码比循环更简洁、更易理解练习逻辑思维巩固函数调用机制结合指针写递归如数组求和、数组遍历既能复习递归又能加深对指针的理解为后续学习打基础。8.2 局限性基础阶段重点规避栈溢出风险递归深度过大时超出调用栈限制导致程序崩溃部分场景效率低未优化的递归在存在大量重复子问题的场景下存在严重的重复计算运行速度极慢调试难度稍高相比循环递归的执行过程更抽象新手调试时需手动模拟调用栈或断点调试。8.3 核心使用原则基础阶段不用追求 “用递归解决所有问题”核心原则简单问题、可拆解的问题用递归练手深层递归、重复子问题多的问题暂时用迭代替代重点是 “吃透基础、巩固思路”而非盲目追求复杂用法。九、递归思想的延伸基础阶段不用太深递归并非孤立知识点是后续学习复杂算法的基础但基础阶段只需知道其和当前 / 后续知识点的简单关联避免增加学习负担。1. 递归与指针核心思路相通两者的核心都是化繁为简指针通过地址直接操作数据简化代码书写和内存操作递归通过拆解问题为子问题简化复杂的逻辑实现。实战结合多写 “指针 递归” 的简单案例如数组求和、数组遍历一举两得融会贯通。2. 递归与循环递归是循环的封装递归的底层是迭代循环的一种封装依赖函数调用栈实现 “循环调用自身”。基础练习尝试将简单的递归转循环如阶乘、1~n 的和加深对两者的理解 —— 所有简单的递归都能改成循环实现。3. 递归与后续学习打基础的核心知识点递归是后续学习数据结构和算法的基础如数据结构二叉树的遍历前序 / 中序 / 后序、链表的反转算法分治算法、回溯算法、深度优先搜索DFS。基础阶段吃透递归后续学习这些内容会事半功倍。十、复习总结与学习建议写给和我一样回头复习的小伙伴学到指针后回头复习递归最大的感悟是递归不用追求 “学得多深”基础阶段吃透定义、核心条件、编写步骤和基础案例避开常见坑就足够了很多之前的困惑会随着后续学习如指针、数据结构的深入慢慢通透。1.核心知识点回顾递归的本质是分治思想 函数调用栈核心要求是终止条件 递推关系执行过程必然是 “先递后归”没有例外编写递归的万能步骤明功能→找终止→推递推→验逻辑一定要先写终止条件再写递推关系基础阶段重点练习阶乘、数组求和结合指针等无重复子问题的递归控制递归深度避开斐波那契这类天生不适合递归的场景。2.适合回头复习的学习建议结合 “学到指针后回头复习” 的经历给小伙伴 3 个实用建议坚持做就能扎实掌握递归基础从最简单的案例入手反复练不要一开始挑战复杂案例重点练阶乘、1~n 的和、指针 数组求和、顺序打印整数这 4 个案例每个案例写 2~3 遍手动模拟执行过程加深理解严格按步骤写代码养成习惯不要凭感觉写递归严格遵循 “四步走” 流程先明确功能再写终止条件接着推导递推关系最后验证避免踩坑结合指针融会贯通多写 “指针 递归” 的简单案例如数组求和、数组遍历、指针版逆序打印字符串既能巩固递归又能复习指针的地址操作、指针移动等基础用法。十一、拓展学习拓展 1青蛙跳台阶问题基础版11.1.1 问题描述一只青蛙要跳上 n 级台阶每次只能跳 1 级或 2 级台阶问跳上 n 级台阶一共有多少种不同的跳法11.1.2 解题思路从「最后一步」反向分析推导出斐波那契递推公式设跳上 n 级台阶有 f (n) 种跳法最后一步只有两种可能跳 1 级前面需跳 n-1 级f (n-1) 种、跳 2 级前面需跳 n-2 级f (n-2) 种总跳法f (n) f (n-1) f (n-2)终止条件n1 时 f (1)1n2 时 f (2)2。11.1.3 C 语言代码#include stdio.h // 青蛙跳台阶递归版基础版存在重复计算n不宜过大 long long jump_step(int n) { if (n 1) { return 1; } else if (n 2) { return 2; } else { return jump_step(n - 1) jump_step(n - 2); } } int main() { int n; printf(请输入台阶数正整数); scanf(%d, n); if (n 1) { printf(错误台阶数需为正整数\n); return 1; } long long num jump_step(n); printf(跳上%d级台阶共有%lld种跳法\n, n, num); return 0; }十二、补充汉诺塔Hanoi Tower问题详解汉诺塔是递归算法的经典问题由法国数学家爱德华・卢卡斯提出核心是通过有限次移动规则将一堆盘子从一个柱子移到另一个柱子解题关键是把复杂问题拆解为规模更小的同类型问题 —— 完美契合递归的分治思想。1.汉诺塔问题描述与核心规则1.1 问题描述有 3 根柱子通常记为 A、B、C和 n 个大小不同的圆盘初始时所有圆盘从小到大叠在 A 柱大的在底部小的在顶部要求将所有圆盘全部移到 C 柱最终叠放顺序和初始一致大下小上。1.2 核心移动规则每次只能移动 1 个圆盘移动过程中任何时刻都不能出现「大圆盘压在小圆盘上」的情况3 根柱子都可作为临时存放圆盘的中间载体如 B 柱常作为 A→C 的中转。1.3 直观示例n3 个圆盘最易理解的基础案例最终需要7 次移动完成能直观看到递归的拆解过程把 A 柱最上面的小圆盘移到 C 柱把 A 柱中间的圆盘移到 B 柱把 C 柱的小圆盘移到 B 柱把 A 柱最大的圆盘移到 C 柱把 B 柱的小圆盘移到 A 柱把 B 柱中间的圆盘移到 C 柱把 A 柱的小圆盘移到 C 柱。2.核心解题思路递归分治最关键汉诺塔的递归思想核心是 「大事化小」—— 要移动 n 个圆盘先解决 n-1 个圆盘的移动问题无论 n 多大拆解步骤只有 3 步这是递归能实现的根本原因。2.1 递归拆解公式记为Hanoi(n, A, B, C)表示n 个盘从源柱 A经中转柱 B移到目标柱 C。第一步把 A 柱上最上面的 n-1 个圆盘经 C 柱中转移到 B 柱 →Hanoi(n-1, A, C, B)暴露最大的圆盘才能单独移动第二步把 A 柱上剩下的 1 个最大圆盘直接移到 C 柱唯一一次移动最大盘递归终止条件的铺垫第三步把 B 柱上暂存的 n-1 个圆盘经 A 柱中转移到 C 柱 →Hanoi(n-1, B, A, C)把小圆盘移到目标柱叠在最大盘上。2.2 递归终止条件当 n1 时只有 1 个圆盘无需中转直接将圆盘从源柱移到目标柱即可 —— 这是递归的「出口」避免无限调用。2.3 核心规律移动 n 个汉诺塔圆盘最少需要 2ⁿ−1 次移动n1 时 1 次n2 时 3 次n3 时 7 次n4 时 15 次符合规律递归的核心是关注「当前要做什么」而非「每一步具体怎么移」不用纠结 n10 时的每一步移动细节只需明确 3 步拆解逻辑计算机会自动处理 n-1、n-2… 的子问题。3.汉诺塔 C 语言代码实现#define _CRT_SECURE_NO_WARNINGS #include stdio.h // 汉诺塔递归函数 // n要移动的圆盘数量 // from源柱子初始A字符表示 // mid中转柱子初始B // to目标柱子初始C void Hanoi(int n, char from, char mid, char to) { // 递归终止条件n1直接从源柱移到目标柱输出移动步骤 if (n 1) { printf(将第%d个圆盘从%c柱移到%c柱\n, n, from, to); return; } // 第一步n-1个盘从from经to中转移到mid Hanoi(n - 1, from, to, mid); // 第二步第n个盘最大的直接从from移到to输出步骤 printf(将第%d个圆盘从%c柱移到%c柱\n, n, from, to); // 第三步n-1个盘从mid经from中转移到to Hanoi(n - 1, mid, from, to); } int main() { int n; printf(请输入汉诺塔的圆盘数量); scanf(%d, n); // 输入合法性判断圆盘数必须是正整数 if (n 1) { printf(错误圆盘数量需为正整数\n); return 1; } // 调用汉诺塔函数n个盘从A经B中转移到C Hanoi(n, A, B, C); // 输出最少移动次数1LLn 避免整数溢出等价于2^n printf(完成%d个圆盘的汉诺塔最少需要%lld次移动\n, n, (1LL n) - 1); return 0; }十三、结尾其实递归的基础学习真的不用太焦虑。我刚开始学习时也经常绕圈、踩坑甚至怀疑自己是不是学不会但学到指针后回头复习才发现很多困惑都迎刃而解了。最后想和大家互动一下你在学到指针后回头复习递归有没有发现哪些之前不懂的地方现在突然通透了或者在练习 “指针 递归” 的案例时遇到了哪些小问题欢迎在评论区留言交流我们一起探讨、一起进步。如果这篇复习总结对你有帮助也欢迎点赞、收藏你的支持就是我继续分享的动力十四、附录基础知识点补充供复习参考1. 常见编程语言的递归深度限制C 语言默认约 1000、Python 默认约 1000、Java 默认约 10000基础阶段控制递归深度在 1000 以内即可避免栈溢出。2. 基础递归转循环示例阶乘以阶乘为例递归转循环的思路简单基础阶段可多尝试加深对递归和循环的理解。// 阶乘递归转循环迭代版 int factorial_loop(int n) { int result 1; for (int i 1; i n; i) { result * i; } return result; }3. 指针基础补充在 “指针 递归” 的案例中arr1表示数组指针向后移动一位指向数组的下一个元素等价于arr[1]是指针的基础用法也是递归中 “缩小问题规模” 的关键。
