函数递归程序设计

什么是递归
递归是编程中的⼀种技术，指的是⼀个函数在其定义内部调用自身。（递归⼀定是依赖于函数的）
核心概括：套娃（大事化小）

2 递归的核⼼要素
⼀个正确的递归函数必须包含两个关键部分：
递归调用（递推阶段）：函数⾃⼰调⽤⾃⼰，每次调⽤时，问题的规模都应该⽐上⼀次更⼩，逐步
逼近⼀个最简单的“基础情况”。
终止条件（基础情况）：⼀个不再进⾏递归调⽤、能直接返回结果的特定条件。如果没有终⽌条
件，递归会⽆限进⾏下去，最终导致栈溢出错误。

典型递归案例
1.求n的阶乘

n = 5

2.顺序打印⼀个整数的每⼀位
输⼊⼀个正整数m，按照顺序打印整数的每⼀位


3.求第n个斐波那契数

我们可以写代码统计⼀下冗余计算的数据，会⾮常的惊⼈。


3.栈溢出
其实递归程序除了可能影响性能之外，还会存在栈溢出的⻛险。
📌 1. 在C语⾔程序中每⼀次函数调⽤，都需要为本次函数调⽤在内存的栈区，申请⼀块内存空
间来保存函数调⽤期间的各种局部变量的值，这块空间被称为运⾏时堆栈，或者函数栈帧。
2. 函数如果不返回，函数对应的栈帧空间就⼀直占⽤，所以如果函数调⽤中存在递归调⽤的话，每⼀次递归函数调⽤都会开辟属于⾃⼰的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。如果采⽤函数递归的⽅式完成代码，递归层次太深，就会浪费太多的栈帧空间，且可能引起栈溢出（stack overflow）的问题。
4. 递归和循环
我们发现递归程序有可能导致栈溢出问题或者性能的问题，那什么解决办法吗？
通常会把递归程序改造成循环的⽅式，⽐如：
4.1 求阶乘


4.3 递归和循环的选择
我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰，但是这些
问题的循环实现往往⽐递归实现效率更⾼。
📌 当⼀个问题⾮常复杂，难以使⽤循环的⽅式实现时，此时递归实现的简洁性便可以补偿它所
带来的运⾏时开销。⼀般情况下，递归的深度<100层，并且不会造成⼤量冗余计算的时候，
可以⼤胆地使⽤递归写法。
当这个问题使⽤递归解决存在明显缺陷的时候，就需要考虑改造成循环的⽅式。
5.递归拓展学习
5.1二分查找
https://gitee.com/cristisiuuu/test_8_3/blob/main/test.c
5.2 汉诺塔问题
（这个问题很有可能是我们儿童时期对递归问题的启蒙，也是基础算法）
A柱上有n个盘⼦，要借助于B柱，挪到C柱上
挪动的过程中，在柱⼦上要保证上的盘⼦⼩，下⾯的盘⼦⼤
思路：把n-1个盘子移到B，将第n个盘子移到C。
再对下面的n-1个盘子重复上述操作。