下载文档原格式
1 如果 n=0,n=1f(n)=nf(n) 如果 n>1图1：以递归的方式计算4的阶乘上图（1）展示了利用递归计算4！的过程。
它也说明了递归过程中的两个基本阶段：递推和回归。
在递推阶段，每一个递归调用通过进一步调用自己来记住这次递归过程。
当其中有调用满足终止条件时，递推结束。
比如，在计算n!时，终止条件是当n=1和n=0，此时函数只需简单的返回1即可。
每一个递归函数都必须拥有至少一个终止条件；否则递推阶段永远不会结束了。
一旦递推阶段结束，处理过程就进入回归阶段，在这之前的函数调用以逆序的方式回归，直到最初调用的函数为止，此时递归过程结束。
以递归的方式计算n的阶乘的函数实现：C函数fact的工作方式如下：它接受一个整数n作为参数，如果n小于0，该函数直接返回0，这代表一个错误。
如果n等于0或1，该函数返回1，这是因为0!和1!都等于1，以上是终止递归的条件。
否则，函数返回n-1的阶乘的n倍。
而n-1的阶乘又会以递归的方式再次调用fact来计算，如此继续。
代码实例（1）：fact.c1/*fact.c*/2#include "fact.h"3int fact(int n){4if (n<0)5return0;6else if(n==0)7return1;8else if(n==1)9return1;10else11return n*f(n-1);12}为理解递归究竟是如何工作的，有必要先看看C语言中函数的执行方式。
我们先来看看C程序在内存中的组织方式（见图2-a）。
基本上，一个可执行程序由4个区域组成：代码段、静态数据区、堆与栈。
代码段包含程序运行时所执行的机器指令。
静态数据区包含在程序生命周期内一直持久的数据，比如全局变量和静态局部变量。
堆包含程序运行时动态分配的存储空间，比如malloc分配的内存。
栈包含函数调用的信息。
当C中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息。
必备算法：递归！⽆论你是前端开发，还是后端开发，都需要掌握它！递归是⼀种⾮常重要的算法思想，⽆论你是前端开发，还是后端开发，都需要掌握它。
在⽇常⼯作中，统计⽂件夹⼤⼩，解析xml⽂件等等，都需要⽤到递归算法。
它太基础太重要了，这也是为什么⾯试的时候，⾯试官经常让我们⼿写递归算法。
本⽂呢，将跟⼤家⼀起深⼊挖掘⼀下递归算法~什么是递归？递归，在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法。
简单来说，递归表现为函数调⽤函数本⾝。
在知乎看到⼀个⽐喻递归的例⼦，个⼈觉得⾮常形象，⼤家看⼀下：❝递归最恰当的⽐喻，就是查词典。
我们使⽤的词典，本⾝就是递归，为了解释⼀个词，需要使⽤更多的词。
当你查⼀个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第⼆个词，可惜，第⼆个词⾥仍然有不懂的词，于是查第三个词，这样查下去，直到有⼀个词的解释是你完全能看懂的，那么递归⾛到了尽头，然后你开始后退，逐个明⽩之前查过的每⼀个词，最终，你明⽩了最开始那个词的意思。
❞来试试⽔，看⼀个递归的代码例⼦吧，如下：递归的特点实际上，递归有两个显著的特征,终⽌条件和⾃⾝调⽤:✿⾃⾝调⽤：原问题可以分解为⼦问题，⼦问题和原问题的求解⽅法是⼀致的，即都是调⽤⾃⾝的同⼀个函数。
✿终⽌条件：递归必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。
结合以上demo代码例⼦，看下递归的特点：递归与栈的关系其实，递归的过程，可以理解为出⼊栈的过程的，这个⽐喻呢，只是为了⽅便读者朋友更好理解递归哈。
以上代码例⼦计算sum（n=3）的出⼊栈图如下：为了更容易理解⼀些，我们来看⼀下函数sum（n=5）的递归执⾏过程，如下：✿计算sum（5）时，先sum（5）⼊栈，然后原问题sum（5）拆分为⼦问题sum（4），再⼊栈，直到终⽌条件sum（n=1）=1，就开始出栈。
✿ sum（1）出栈后，sum（2）开始出栈，接着sum（3）。
✿最后呢，sum（1）就是后进先出，sum（5）是先进后出，因此递归过程可以理解为栈出⼊过程啦~递归的经典应⽤场景哪些问题我们可以考虑使⽤递归来解决呢？即递归的应⽤场景⼀般有哪些呢？✿阶乘问题✿⼆叉树深度✿汉诺塔问题✿斐波那契数列✿快速排序、归并排序（分治算法体现递归）✿遍历⽂件，解析xml⽂件递归解题思路解决递归问题⼀般就三步曲，分别是：✿第⼀步，定义函数功能✿第⼆步，寻找递归终⽌条件✿第⼆步，递推函数的等价关系式这个递归解题三板斧理解起来有点抽象，我们拿阶乘递归例⼦来喵喵吧~1、定义函数功能定义函数功能，就是说，你这个函数是⼲嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀？⽐如你需要解决阶乘问题，定义的函数功能就是n的阶乘，如下：2、寻找递归终⽌条件递归的⼀个典型特征就是必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。
栈在递归中的作用栈是一种具有特殊性质的线性数据结构，在其中元素的插入和删除操作只能在栈的顶部进行。
栈的特点是元素按照后进先出的顺序进行处理，即最后插入到栈中的元素最先被访问到。
递归是一种程序设计技巧，通过一个函数在其定义中调用自身来解决问题。
递归函数在解决问题时以一种分而治之的办法，将原始问题划分为较小的子问题，并通过解决子问题来解决原始问题。
那么，栈在递归中起到了什么作用呢？一、存储临时变量：递归函数在每一次调用自身时都会入栈，该栈用来保存每个递归调用时的临时变量。
在递归函数内部定义的变量会保存在栈中，每次函数调用时，这些局部变量都会被压入栈中。
当函数的递归调用完成后，栈中保存的该函数的局部变量会被弹出，以便为下一个递归调用或其他操作提供内存空间。
这样，栈起到了一个保存临时变量的作用。
二、存储函数调用的返回地址：在递归调用时，每次调用后都需要返回到上一层调用处。
栈的另一个作用是存储函数调用的返回地址。
当一个函数调用了自身，并进行了递归调用时，当前函数的上下文信息（包括函数指针、参数和局部变量等）都会被保存在栈中，然后在递归调用完成后，栈中保存的上下文信息将被弹出，返回到上一层函数的下一条执行指令的位置，继续执行下去。
三、维护递归层次关系：递归调用时，每次调用自身都需要将当前的状态保存在栈中，这样可以保留每一次递归调用的上下文信息。
栈的深度也反映了递归的层次关系。
当递归调用层数很大时，栈的深度也会相应增加。
四、确保函数调用的正确性：栈在递归中还发挥了确保函数调用的正确性的作用。
每一次递归调用都会将当前的状态保存在栈中，包括参数、局部变量、返回地址等信息。
这样，即使在递归调用过程中发生了其他函数的调用，当递归调用完成后，栈中保存的状态信息都能够正确恢复，确保程序的正确执行。
总结来说，栈在递归中起到了存储临时变量、存储函数调用的返回地址、维护递归层次关系以及确保函数调用的正确性等作用。
栈的使用使递归函数能够按照正确的顺序进行递归调用，并在递归调用完成后正确返回上一层函数的下一条执行指令的位置。
递归算法原理
递归是一种算法设计技巧，它的原理是通过将一个问题分解成一个或多个规模较小但类似于原问题的子问题来解决。
递归算法通过反复调用自身来解决这些子问题，直到子问题的规模足够小并可以直接解决为止。
递归算法的主要思想是将问题转化为更小的同类问题的子问题，并在每一次递归调用中将问题的规模减小。
递归算法需要定义一个基准情况，即问题的最小规模情况，当问题达到基准情况时，递归的调用将停止，得到最终的解。
当使用递归算法时，需要注意以下几点：
1. 递归的结束条件：为了避免无限递归，递归函数必须定义结束条件，即基准情况。
2. 递归调用：在函数内部调用自身来解决规模较小的子问题。
3. 子问题规模的减小：每次递归调用时，子问题的规模应该比原问题要小。
4. 递归栈：在每次递归调用时，系统会将当前的函数调用信息存储在递归栈中，当递归调用结束后，系统将会按照递归栈的顺序逐个弹出函数调用信息，直到返回最终的解。
递归算法在解决某些问题时非常有效，例如树和图的遍历、排列组合、分治算法等。
然而，递归算法也存在一些缺点，例如
递归调用会消耗较多的内存空间和时间复杂度较高等问题，因此在实际应用中需要根据具体情况来选择是否使用递归算法。
递归算法详解完整版递归算法是一种重要的算法思想，在问题解决中起到了很大的作用。
它通过将一个大问题划分为相同或类似的小问题，并将小问题的解合并起来从而得到大问题的解。
下面我们将详细介绍递归算法的定义、基本原理以及其应用。
首先，我们来定义递归算法。
递归算法是一种通过调用自身解决问题的算法。
它通常包括两个部分：基础案例和递归步骤。
基础案例是指问题可以被直接解决的边界情况，而递归步骤是指将大问题划分为较小问题并通过递归调用自身解决。
递归算法的基本原理是"自顶向下"的思维方式。
即从大问题出发，不断将问题划分为较小的子问题，并解决子问题，直到达到基础案例。
然后将子问题的解合并起来，得到原始问题的解。
递归算法的最大特点是简洁而优雅。
通过将复杂问题分解为简单问题的解决方式，可以大大减少代码的复杂程度，提高程序的效率和可读性。
但是递归算法也有一些缺点，包括递归深度的限制和复杂度的不确定性。
过深的递归调用可能导致栈溢出，而不合理的递归步骤可能导致复杂度过高。
递归算法有许多应用场景，我们来介绍其中一些典型的应用。
1.阶乘问题：计算一个数的阶乘。
递归算法可以通过将问题划分为更小的子问题来解决。
例如，n的阶乘可以定义为n乘以(n-1)的阶乘。
当n 等于1时，我们可以直接返回1作为基础案例。
代码如下：```int factorial(int n)if (n == 1)return 1;}return n * factorial(n - 1);```2.斐波那契数列问题：求斐波那契数列中第n个数的值。
斐波那契数列的定义是前两个数为1，然后从第三个数开始，每个数都是前两个数的和。
递归算法可以通过将问题划分为两个子问题来解决。
当n等于1或2时，直接返回1作为基础案例。
代码如下：```int fibonacci(int n)if (n == 1 ， n == 2)return 1;}return fibonacci(n - 1) + fibonacci(n - 2);```3.二叉树问题：对于给定的二叉树，递归算法可以通过递归调用左子树和右子树的解来解决。
数据结构之递归Ⅲ递归的三⼤要素// 算 n 的阶乘(假设n不为0)int f(int n){if(n <= 2){return n;}}第三要素：找出函数的等价关系式第三要素就是，我们要不断缩⼩参数的范围，缩⼩之后，我们可以通过⼀些辅助的变量或者操作，使原函数的结果不变。
例如，f(n) 这个范围⽐较⼤，我们可以让 f(n) = n * f(n-1)。
这样，范围就由 n 变成了 n-1 了，范围变⼩了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。
说⽩了，就是要找到原函数的⼀个等价关系式，f(n) 的等价关系式为 n * f(n-1)，即f(n) = n * f(n-1)。
这个等价关系式的寻找，可以说是最难的⼀步了，如果你不⼤懂也没关系，因为你不是天才，你还需要多接触⼏道题，我会在接下来的⽂章中，找 10 道递归题，让你慢慢熟悉起来。
找出了这个等价，继续完善我们的代码，我们把这个等价式写进函数⾥。
如下：// 算 n 的阶乘(假设n不为0)int f(int n){if(n <= 2){return n;}// 把 f(n) 的等价操作写进去return f(n-1) * n;}⾄此，递归三要素已经都写进代码⾥了，所以这个 f(n) 功能的内部代码我们已经写好了。
这就是递归最重要的三要素，每次做递归的时候，你就强迫⾃⼰试着去寻找这三个要素。
还是不懂？没关系，我再按照这个模式讲⼀些题。
有些有点⼩基础的可能觉得我写的太简单了，没耐⼼看？少侠，请继续看，我下⾯还会讲如何优化递归。
当然，⼤佬请随意，可以直接拉动最下⾯留⾔给我⼀些建议，万分感谢！Ⅲ案例1：斐波那契数列斐波那契数列的是这样⼀个数列：1、1、2、3、5、8、13、21、34....，即第⼀项 f(1) = 1,第⼆项 f(2) = 1.....,第 n 项⽬为 f(n) = f(n-1) + f(n-2)。
求第 n 项的值是多少。
栈与递归的关系姓名：郭小兵学号：1007010210专业：信息与计算科学院系：理学院指导老师：彭长根2012年10月17日栈与递归的关系郭小兵摘要递归是计算机科学中一个极为重要的概念,许多计算机高级语言都具有递归的功能,对于初学计算机者来讲,递归是一个简单易懂的概念,但真正深刻理解递归,正确自如的运用递归编写程序却非易事,本文通过一些实例来阐述递归在计算机内的实现及递归到非递归的转换,也许使读者能加深对递归的理解。
关键词栈递归非递归引言递归是一种程序设计的方式和思想。
计算机在执行递归程序时，是通过栈的调用来实现的。
栈，从抽象层面上看，是一种线性的数据结构，这中结构的特点是“先进后出”，即假设有a，b，c三个元素，依次放某个栈式存储空间中，要从该空间中拿到这些元素，那么只能以c、b、a的顺序得到。
递归程序是将复杂问题分解为一系列简单的问题，从要解的问题起，逐步分解，并将每步分解得到的问题放入“栈”中，这样栈顶是最后分解得到的最简单的问题，解决了这个问题后，次简单的问题可以得到答案，以此类推。
分解问题是进栈（或者说压栈）的过程，解决问题是一个出栈的过程。
科学家对栈与递归都做了很多深入的研究，研究表明“递归算法和栈都有后进先出这个性质，基本上能用递归完成的算法都可以用栈完成，都是运用后进先出这个性质的”这个性质可用于进制的转换。
与汇编程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需过栈来进行。
递归是计算科学中一个极为重要的概念。
许多计算机高级语言都具有递归的功能，本文将通过一些是例来阐述递归在计算机内的实现及递归到非递归的转换，也许能加深对递归的理解。
递归是某一事物直接或间接地由自己完成。
一个函数直接或间接地调用本身，便构成了函数的递归调用，前者称之为直接递归调用，后者为间接递归调用。
递归会使某些看起来不容易解决的问题变得容易解决。
