第5章递归第1讲-什么是递归

递归算法及经典例题详解
1.什么是递归
递归简单来说就是在运行过程中不断调用自己，直到碰到终止条件，返回结果的过程。

递归可以看作两个过程，分别是递和归。

递就是原问题把要计算的结果传给子问题；归则是子问题求出结果后，把结果层层返回原问题的过程。

下面设一个需要经过三次递归的问题，为大家详细看一下递归的过程：当然，现实中我们遇到递归问题是不会按照图中一样一步一步想下来，主要还是要掌握递归的思想，找到每个问题中的规律。

2.什么时候使用递归
递归算法无外乎就是以下三点：1.大问题可以拆分为若干小问题2.原问题与子问题除数据规模不同，求解思路完全相同3.存在递归终止条件
而在实际面对递归问题时，我们还需要考虑第四点：
当不满足终止条件时，要如何缩小函数值并让其进入
下一层循环中
3.递归的实际运用（阶层计算）
了解了大概的思路，现在就要开始实战了。

下面我们来看一道经典例题：
求N的阶层。

首先按照思路分析是否可以使用递归算法：
1.N！可以拆分为（N-1）！*N
2.（N-1）！与N！只有数字规模不同，求解思路相同
3.当N=1时，结果为1，递归终止
满足条件，可以递归：
publicstaticintFactorial(int num){if(num==1){return num;}return num*Factorial(num-1);}
而最后的return，便是第四步，缩小参数num的值，让递归进入下一层。

一般来说，第四步往往是最难的，需要弄清该如何缩
小范围，如何操作返回的数值，这一步只能通过不断
地练习提高了（当然如果你知道问题的数学规律也是
可以试出来的）。

递归公认的递归(Recursion)的标准定义是非常难理解的：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。

递归一词很少有过专业的定义，因此本文不在于去解释上一段文字的意义。

虽然概念抽象，但递归其本身是不难理解的。

通过本文的介绍，读者不一定能深入了解递归，只要能通过具体的例子模模糊糊地知道一些递归的思想和用途就可以了。

究竟什么是递归呢？其实，递归就是大鱼吃小鱼，就是一条蛇咬住自己的尾巴。

递归是指一样东西自己包含了自己。

对于这一点，拿“谢尔品斯基地毯”(Sierpinski Gasket)来说明是最恰当不过的了。

曲线在几何学中的概念很好理解，就是只有长度而没有宽度的线条。

数学中有各种各样的曲线，如圆、直线、抛物线、双曲线、正弦曲线等。

它们都可以用一定的方法画出来。

例如，圆可以用圆规画出来，正弦曲线也可以用机器边在纸带上往复记号边拉纸带的方法画出来。

事实上却没那么麻烦，画曲线有一个最常用的“万能方法”——似乎所有的曲线都可以用“描点法”画出，因为曲线没有宽度嘛，一个一个的点连起来，随便多奇怪的曲线都应该能画出。

但随着数学的发展，这一点遭到了置疑。

波兰数学家谢尔品斯基就想出了一个的确是一种曲线但永远无法画出的图形。

他构造这种曲线的方法就运用了递归。

随便找了一个正方形，把它分成3×3规格的相等的9个小正方形，然后把正中间的那一个挖掉。

现在就只剩周围的八个小正方形了。

接着重复这个过程，把8个小正方形的每一个都分成更小的9份，并挖掉它中间的那个。

现在得到的就有8×8=64个正方形了。

把这64个正方形继续这样划分，并且无限制的继续下去。

这就是递归的思想，自己包含了自己，而后面的自己又包含了规模更小的自己。

这样递归下去是没完的，因此最终得到的会是没有宽度的线条。

这符合曲线的定义，但显然它是没办法画出来的。

在现实生活中，递归的现象也是可以见到的。

递归与高等数学一、递归函数递归函数是一种数学函数，它在其定义或行为中直接或间接地调用自身。

递归函数通常用于解决一些可以分解为更小的子问题的问题。

递归函数可以分为两类：基本递归函数和递归函数。

基本递归函数是直接解决问题的函数，而递归函数则是通过调用自身来解决问题的函数。

在高等数学中，许多问题可以通过使用递归函数来解决。

例如，在微积分中，许多积分和级数可以通过递归方法进行计算。

此外，在实数和复数分析中，许多函数可以通过递归函数进行展开和逼近。

二、递归数列递归数列是一种特殊的数列，它可以通过一系列规则生成。

常见的递归数列包括斐波那契数列、卢卡斯数列等。

递归数列在数学和计算机科学中都有广泛的应用。

在高等数学中，递归数列可以用于解决一些与序列相关的问题。

例如，在概率论和统计学中，一些概率分布可以通过递归数列进行描行解决。

三、递归方程递归方程是一种描述自然规律的数学工具，它是通过递归函数定义的等式或系统。

常见的递归方程包括人口动态模型、斐波那契序列等。

在高等数学中，递归方程可以用于解决一些与时间相关的问题。

例如，在微分方程和差分方程中，一些问题可以通过递归方程进行描述和解决。

此外，在控制理论和系统理论中，一些系统可以通过递归方程进行建模和分析。

四、递归级数递归级数是具有特定模式的数字序列或数字集的级数表示。

它与级数、级数定理、积分级数以及算术、几何和三角级数等都有密切的关系。

在高等数学中，递归级数可以用于解决一些与数字相关的问题。

例如，在离散概率论和统计学中，一些概率分布可以通过递归级数进数进行解决。

五、递归图论图论是研究图（由顶点和边构成的图形）的数学理论。

在图论中，图是由顶点（或节点）和连接这些顶点的边构成的。

递归图论则是使用递归来定义或描述图的理论。

在计算机科学中，这可以用于计算机算法、数据结构和其他相关的领域。

例如，一种常用的数据结构是二叉堆（Binary Heap），它可以看作是一个完全二叉树，并且每个节点都有两个子节点（除了叶节点）。

递归函数解释
一、递归定义
递归函数是指一个函数在其定义域内，存在某个或某些子集作为其自身的输入，也就是一个函数直接或间接调用自身的一种过程。

通常递归函数的定义会包含两部分：基本情况和递归情况。

二、基本情况
基本情况也被称为基线条件，是递归函数的结束条件。

基本情况决定了递归何时停止，它必须是直接可求解的情况。

基本情况是递归函数的根，其他递归情况都由它导出。

三、递归转化
递归转化是将问题转化为更小的同类问题的一种策略。

在递归函数中，每一个递归调用都是为了解决一个更小的子问题，以便于通过这些子问题的解来找到原问题的解。

四、递归终止
递归终止是指函数在完成一系列递归调用后，最终达到基本情况并返回结果的过程。

递归终止是递归函数的终点，也是递归函数开始返回结果的地方。

五、递归层次
递归层次是指函数在执行过程中所经历的递归深度。

每一个递归调用都会增加一层的递归深度，直到达到基本情况并返回结果，然后开始逐层返回，直到完成所有递归调用。

理解递归层次有助于更好地理解递归函数的执行过程和时间复杂度。

什么是递归？递归（Recursion）是一种编程技术，其中一个函数调用自身来解决问题。

递归是通过将问题分解成更小的子问题来解决复杂问题的一种方法。

这种自我调用的过程在每次调用中都会处理一个更小的问题，直到达到基本情况（终止条件），然后逐步返回结果，最终解决整个问题。

递归的核心思想是将复杂问题分解成更小规模的相同问题。

每次递归调用都会将问题的规模减小，直到问题达到一定的规模，可以直接解决。

这个基本情况通常是一个简单且不再需要递归的情况。

递归的实现通常包括以下几个要素：1. 基本情况：基本情况是递归调用的终止条件。

当问题的规模减小到一定程度，可以直接解决时，递归将停止。

在基本情况下，函数通常直接返回结果而不再进行递归调用。

2. 递归调用：递归函数在解决问题的过程中会调用自身来处理更小规模的子问题。

递归函数通过传递问题的子集或更小的输入来减小问题的规模。

递归调用将重复进行，直到达到基本情况。

3. 问题的规模减小：递归函数通过每次调用将问题的规模减小来逐步解决问题。

这通常涉及到在每次递归调用中使用不同的输入或参数。

问题的规模必须在每次递归调用中减小，否则递归将无法终止，导致无限循环（无穷递归）。

递归的一个典型示例是计算阶乘。

阶乘是指从1到某个正整数之间所有整数的乘积。

使用递归，我们可以将阶乘问题分解为更小的子问题，直到达到基本情况。

例如，计算5的阶乘（5!）可以使用递归的方式来实现：```factorial(n):if n == 0: // 基本情况return 1else:return n * factorial(n-1) // 递归调用```在上面的示例中，当n等于0时，递归调用将停止，返回1作为结果。

否则，函数将n与n-1的阶乘相乘，并继续递归调用，直到达到基本情况。

递归函数需要小心处理，确保递归调用能够终止，并且问题的规模在每次递归调用中减小。

否则，递归可能会导致堆栈溢出或无限循环的问题。

递归在许多算法和数据结构问题中都有应用，例如树的遍历、图的搜索、排序算法等。

递归的理解
递归是一种算法或编程技巧，它通过自身调用来解决问题，常常被用来处理具有递归结构的问题。

在递归中，一个函数或子程序会重复调用自身，直到达到终止条件为止。

递归的理解需要注意以下几个方面：
首先，递归必须有一个终止条件，否则会陷入死循环。

终止条件是指递归应该停止的条件，一旦达到这个条件，递归就会结束。

其次，在递归过程中，每一级递归都需要相同的处理方式。

也就是说，每次递归都要按照同样的逻辑进行处理，直到达到终止条件。

第三，在递归中，每次调用都会有一定的开销，包括函数调用、参数传递和栈空间的分配等。

因此，在使用递归时，需要注意内存的使用和性能的优化。

最后，递归常常被用来解决复杂的问题，例如快速排序、归并排序、二叉树的遍历等。

但是，如果不恰当地使用递归，会导致栈溢出等问题。

因此，在使用递归时，需要仔细考虑其适用性和实现方式。

总之，递归是一种非常有用的算法思想，理解递归需要掌握其基本原理和注意事项，才能正确地应用到实际问题中。

- 1 -。

递归名词解释
递归：
1、概念：递归是一种反复出现的算法，它将一个大问题拆分成若干小
问题，并且使用结果解决大问题，在解决大问题时候可以多次重复调
用自身以达到解决问题的目的。

2、定义：递归是一种编程技术，它提供了一种可以让程序创建动态的、多层的数据结构的一种方法，也就是用较少的语句可以实现数据结构
的表示。

3、原理：递归调用的原理是多次执行同一个程序段，在程序段内部，
对已知的特殊情况保存结果，减少运算量，并根据条件调用自身以解
决整个问题。

4、特点：
* (1)可以根据已知条件简化问题
* (2)可以多次调用自身、产生迭代结果，在一次调用中展开多次迭代，以实现复杂数据结构的表示
* (3)可以在程序段中使用条件语句，在特定条件真伪时返回特定的结
果
* (4)可以实现交替操作，多次调用自身，每次执行的逻辑可能不一样。

5、应用场景：
* (1)求解较复杂的数学问题，比如斐波那契数列问题、汉诺塔问题等* (2)求解复杂算法，比如快速排序、归并排序等
* (3)实现迭代计算，让程序可以定义无限长度的数据结构。

数学中的递归关系与递归公式数学中的递归关系与递归公式是一种重要的数学工具，被广泛应用于各个领域，包括计算机科学、经济学、物理学等。

本文将就递归关系和递归公式的概念、特点以及应用领域进行探讨。

一、递归关系的概念与特点递归关系是指在定义中依赖自身的关系。

换句话说，当前的值取决于前面的值。

在数学中，递归关系常常用于描述数列、集合以及函数之间的关系。

一个典型的递归关系可以用如下的数列来说明：F(n) = F(n-1) + F(n-2)，其中F(1)=1，F(2)=1。

在这个数列中，每一个数都是前两个数的和。

递归关系的特点在于它能够将较大的问题转化为较小的子问题，并通过不断地迭代求解子问题来得到最终的结果。

递归关系有以下几个重要的特点：1. 递归关系需要一个或多个初始条件，也称为基本情况。

在上述例子中，F(1)=1和F(2)=1即为初始条件，没有初始条件的递归关系将无法求解。

2. 递归关系必须能够在每一步中将问题规模缩小。

这保证了问题在经过有限次迭代后能够达到基本情况。

3. 递归关系可能存在多个解，每一个解都是基于不同的初始条件得到的。

4. 递归关系的求解通常通过递归公式来实现。

二、递归公式的概念与求解方法递归公式是一种用于求解递归关系的数学表达式。

它用于将问题的较大实例转化为较小实例的解。

通常情况下，递归公式由递归关系的定义式推导得到。

以斐波那契数列为例，递归关系F(n) = F(n-1) + F(n-2)中的递归公式为F(n) = F(n-1) + F(n-2)，其中F(1)=1，F(2)=1。

通过递归公式，我们可以直接计算出数列中任意位置的值，而无需通过逐步迭代求解。

除了直接求解递归关系外，递归公式还可以用于证明数学定理和推导数学结论。

通过递归公式，我们可以建立数学模型，进而解决实际问题。

三、递归关系与递归公式的应用1. 计算机科学中的递归关系与递归公式在计算机科学中，递归关系和递归公式被广泛应用于算法分析和设计中。

计算机科学的新学生通常难以理解递归程序设计的概念。

递归思想之所以困难，原因在于它非常像是循环推理（circular reasoning）。

它也不是一个直观的过程；当我们指挥别人做事的时候，我们极少会递归地指挥他们。

对刚开始接触计算机编程的人而言，这里有递归的一个简单定义：当函数直接或者间接调用自己时，则发生了递归。

递归的经典示例计算阶乘是递归程序设计的一个经典示例。

计算某个数的阶乘就是用那个数去乘包括 1 在内的所有比它小的数。

例如，factorial(5) 等价于 5*4*3*2*1，而factorial(3) 等价于 3*2*1。

阶乘的一个有趣特性是，某个数的阶乘等于起始数（starting number）乘以比它小一的数的阶乘。

例如，factorial(5) 与 5 * factorial(4) 相同。

您很可能会像这样编写阶乘函数：清单 1. 阶乘函数的第一次尝试int factorial(int n){return n * factorial(n - 1);}不过，这个函数的问题是，它会永远运行下去，因为它没有终止的地方。

函数会连续不断地调用 factorial。

当计算到零时，没有条件来停止它，所以它会继续调用零和负数的阶乘。

因此，我们的函数需要一个条件，告诉它何时停止。

由于小于 1 的数的阶乘没有任何意义，所以我们在计算到数字 1 的时候停止，并返回 1 的阶乘（即 1）。

因此，真正的递归函数类似于：清单 2. 实际的递归函数int factorial(int n){if(n == 1){return 1;}else{return n * factorial(n - 1);}}可见，只要初始值大于零，这个函数就能够终止。

停止的位置称为基线条件（base case）。

基线条件是递归程序的最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果。

所有递归程序都必须至少拥有一个基线条件，而且必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间。

通俗易懂读懂递归什么是递归？如果按照字面意义来解释，递归就是自我从属的行为。

在计算机科学中，递归是指一个函数或者算法调用自身的过程。

这个过程通常通过将任务分解成更小的子问题来实现。

那么，为什么需要递归？递归可以提高代码的可读性和可维护性。

它通常用于解决复杂的问题，这些问题可以被分成较小的，相似的子问题。

递归代码比非递归代码更少，也更容易理解。

同时，递归可以通过多种方式优化。

递归的基本原则递归的基本原则是将一个问题分解成更小的问题，直到问题可以被直接解决。

然后将所有子问题的结果组合起来，解决原始问题。

这个过程可以归结为三个步骤：1. 找到递归基例（base case）。

递归基例是指问题可以被直接解决的情况。

如果问题不能被分解到更小的问题，就需要一个递归基例来停止递归调用。

2. 找到递归规则（recursion rule）。

递归规则是指如何将原始问题分解成更小的问题。

递归规则必须使得问题规模减小，并且必须最终达到递归基例。

3. 讲递归规则和递归基例转化为代码。

这个过程需要定义递归函数，并在函数中调用自己。

当递归达到递归基例时，函数停止调用自己并返回结果。

递归的优缺点递归的优点包括代码易于编写和理解，它能简化解决复杂问题的过程，并且利用起来非常方便。

递归的缺点包括效率较低，容易受限于调用堆栈深度的限制，以及时间和空间的成本高。

使用递归的场合递归函数通常用于解决树形结构或图形结构的问题，也可用于处理迭代子程序，或者使代码更简洁易懂。

递归还可以用于组合问题，例如迷宫问题和八皇后问题。

总结递归是计算机科学中的基本概念，它可以被用于解决复杂的问题，并且被广泛应用在许多领域中。

但是，使用递归需要注意其效率和调用堆栈深度的限制。

递归的概念
一、递归（R e c u r s i o n）的概念
如果一个对象部分地由自己组成，或者是按它自已定义的，则称为是递归的。

递归不仅在数学中会遇到，在日常生活中也可以遇到。

请看下面的图片：
二、递归算法
直接或间接地调用自身的算法称为递归算法。

用函数自身给出定义的函数称为递归函数。

在计算机算法设计与分析中，递归技术是十分有用的。

使用递归技术往往使函数的定义的算法的描述简洁且易于理解。

有些数据结
构如二叉树等，由于其本身固有的递归特性，特别适合用递归的形
式来描述。

另外，还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析。

递归算法一般用于解决三类问题：
(1)数据的定义形式是按递归定义的。

这类递归问题往往又可转化成递推算法，递归边界作为递推的边界条件。

比如阶乘的定义：
(式
2-1)
又如裴波那契（F i b o n a c c i）数列的定义：
(式
2-2)
(2)问题解法按递归算法实现。

例如回溯等。

(3)数据的结构形式是按递归定义的。

如树的遍历，图的搜索等。

递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。

在递归调用的过程当中系统为每一层的返回点、局部量等开辟
了栈来存储。

递归次数过多容易造成栈溢出等。

一：什么是递归所谓递归，简单点来说，就是一个函数直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

我们可以把”递归“比喻成“查字典“，当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词。

可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。

（摘自知乎的一个回答）我们以阶乘作为：int Factorial(int n){if (n == 0) return 1;returnn * Factorial(n - 1);}二：递归与栈的关系常常听到“递归的过程就是出入栈的过程”，这句话怎么理解？我们以上述代码为例，取 n=3，则过程如下：•第1~4 步，都是入栈过程，Factorial(3)调用了Factorial(2)，Factorial(2)又接着调用Factorial(1)，直到Factorial(0)；•第5 步，因0 是递归结束条件，故不再入栈，此时栈高度为4，即为我们平时所说的递归深度；•第6~9 步，Factorial(0)做完，出栈，而Factorial(0)做完意味着Factorial(1)也做完，同样进行出栈，重复下去，直到所有的都出栈完毕，递归结束。

每一个递归程序都可以把它改写为非递归版本。

我们只需利用栈，通过入栈和出栈两个操作就可以模拟递归的过程，二叉树的遍历无疑是这方面的代表。

但是并不是每个递归程序都是那么容易被改写为非递归的。

某些递归程序比较复杂，其入栈和出栈非常繁琐，给编码带来了很大难度，而且易读性极差，所以条件允许的情况下，推荐使用递归。

三：如何思考递归在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的验证之中，比如上面提及的阶乘，求解Factorial(n)时，我们总会情不自禁的发问，Factorial(n-1)可以求出正确的答案么？接着我们就会再用Factorial(n-2)去验证，，，不停地往下验证直到Factorial(0)。

什么是递归？递归（Recursion），是计算机科学与技术领域中一种常见的算法思想。

在数学和计算机领域中，递归主要是指在函数的定义中使用函数自身的方法。

顾名思义，递归主要包含两个意思，递和归，这个是递归思想的精华所在。

递归就是有去（递去）有回（归来）。

“有去” 是指递归问题可以分解成若干个规模较小、与原问题形式相同的子问题，这些子问题可以和原问题用相同的方法来求解。

“有回” 是指这些问题的演化过程是一个从大到小，并且最终会有一个明确的终点，一旦达到终点，就可以从终点原路返回，解决原问题。

更为直接的说法就是：递归的基本思想就是把大问题转化为相似的小问题解决。

特别是在程序中的函数实现时，大问题的解决方案和小问题是一模一样的，所以就产生解决一个问题会调用函数本身的情况，这个也是递归的定义。

3. 用数学归纳法理解递归思想很多时候，大家都在思考递归在数学上面应该如何表示了，毕竟对于数学的简单理解比起我们直接写代码起来还是要简单很多的。

观察递归，我们会很容易发现递归的数学模型类似于数学归纳法，这个在高中的数列里面就已经开始应用了。

数学归纳法常见的描述如下最简单和常见的数学归纳法是证明当n等于任意一个自然数时某命题成立。

证明分下面两步：证明当n= 1 时命题成立。

假设n=m时命题成立，那么可以推导出在n=m+1 时命题也成立。

（m代表任意自然数）数学归纳法适用于将需要解决的原问题转换为解决他的子问题，而其中的子问题又可以变成子问题的子问题，而且这些问题都是同一个模型，可以用相同的处理逻辑归纳处理。

当然有一个是例外的，就是归纳结束的那一个处理方法不能适用于其他的归纳处理项。

递归同样的是将大的问题分解成小问题处理，然后会有一个递归的终止条件，满足终止条件之后开始回归。

数学里面有一个很有名的斐波那契数列，我们在编程求解斐波那契数列的时候就会用到递归的思想，在后续的内部中会具体讲到。

4. 递归的三要素在明确递归的定义及数学模型之后，我们需要掌握递归的三要素：1.递归终止条件；2.递归终止时候的处理方法；3.递归中重复的逻辑提取，缩小问题规模。