下载文档原格式
递归算法及经典例题详解
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的值，让递归进入下一层。
一般来说，第四步往往是最难的，需要弄清该如何缩
小范围，如何操作返回的数值，这一步只能通过不断
地练习提高了（当然如果你知道问题的数学规律也是
可以试出来的）。
数据结构递归算法例子数据结构中的递归算法是指一个函数在其定义中调用自身的过程。
递归算法在解决一些问题时非常有效，因为它可以将复杂的问题分解为更小的子问题来解决。
在本文中，我将列举一些常见的数据结构递归算法的例子，来帮助读者更好地理解递归的概念和应用。
1. 阶乘算法：计算一个正整数的阶乘。
阶乘的定义是n! = n * (n-1) * (n-2) * ... * 1。
使用递归算法可以简洁地实现阶乘的计算，代码如下：```pythondef factorial(n):if n == 0:return 1else:return n * factorial(n-1)```2. 斐波那契数列：斐波那契数列是一个数列，其中每个数字是前两个数字之和。
使用递归算法可以很容易地计算斐波那契数列的第n 个数字，代码如下：```pythondef fibonacci(n):if n <= 1:return nelse:return fibonacci(n-1) + fibonacci(n-2)```3. 二叉树遍历：二叉树是一种常见的数据结构，它包含一个根节点和每个节点最多有两个子节点。
使用递归算法可以实现二叉树的前序、中序和后序遍历。
下面是一个中序遍历的例子：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef inorderTraversal(root):if root:inorderTraversal(root.left)print(root.val)inorderTraversal(root.right)```4. 链表反转：链表是一种常见的数据结构，通过指针将一组节点连接在一起。
使用递归算法可以反转一个链表，即将链表的指针方向改变。
递归算法及经典递归例子代码实现递归算法是一种在函数体内调用函数本身的算法。
通过递归，问题可以被分解为规模更小的子问题，直到达到基本情况，然后将所有的子问题的解合并起来，得到原始问题的解。
递归算法的实现通常包含两个要素：基本情况和递归调用。
基本情况是指不能再进一步分解的情况，一般是针对问题的最小输入。
递归调用是指在解决子问题之后，将问题规模缩小，然后调用自身来解决更小规模的问题。
下面将介绍三个经典的递归例子，并给出相应的代码实现。
1.阶乘计算：阶乘是指从1到给定的数字n之间所有整数的乘积。
它是递归问题的经典例子之一```pythondef factorial(n):if n == 0:return 1else:return n * factorial(n - 1)```在阶乘的递归实现中，基本情况是n等于0时，返回1、递归调用是将问题规模变为n-1，然后将得到的结果与n相乘。
通过递归调用，可以一直计算到n为1，然后将每个阶乘结果逐步合并返回，最终得到n的阶乘。
2.斐波那契数列：斐波那契数列是指从0和1开始，后续的数字都是前两个数字之和。
```pythondef fib(n):if n <= 0:return 0elif n == 1:return 1else:return fib(n - 1) + fib(n - 2)```在斐波那契数列的递归实现中，基本情况是n小于等于0时返回0，n等于1时返回1、递归调用是将问题规模分为两个子问题，分别计算n-1和n-2的斐波那契数，然后将两个子问题的结果相加返回。
通过递归调用，可以一直计算到n为0或1，然后将每个斐波那契数逐步合并返回，最终得到第n个斐波那契数。
3.二叉树遍历：二叉树遍历是指按照一定的顺序访问二叉树的所有节点。
```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef inorderTraversal(root):if root is None:return []else:return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)```在二叉树的中序遍历的递归实现中，基本情况是判断当前节点是否为空，如果为空则返回一个空列表。
递归题型总结全文共四篇示例，供读者参考第一篇示例：本文将对递归题型做一个总结，包括递归的基本原理、递归的模板，以及一些常见的递归题型，希望读者可以通过本文对递归有一个更全面的了解和掌握。
一、递归的基本原理递归是指在程序执行过程中调用自身的一种方法，递归的实现需要满足三个条件：递归调用、递归结束条件和递归返回值。
其中递归调用是指在问题规模不断缩小的情况下通过反复调用自身来解决问题，递归结束条件是指在问题规模缩小到一定程度时停止递归，递归返回值是指在递归结束时返回最终的结果。
在进行递归实现时，需要注意递归的层数和空间复杂度，由于递归会占用额外的栈空间，当递归层数过深时可能会导致栈溢出的问题，因此在设计递归算法时需要考虑到空间复杂度的问题，并尽可能避免递归层数过深。
二、递归的模板在解决递归问题时，通常需要依据递归的性质设计一个递归函数，一般而言递归函数的设计包括三个部分：递归结束条件、递归调用和递归返回值。
在设计递归函数时需要关注这三个部分，并尽可能让递归函数的结构清晰明了。
下面是一个递归的模板：def recursion(problem, param1, param2, ...):#递归结束条件if problem is None or problem is invalid:return some_value#递归调用sub_problem = split_problem(problem)result1 = recursion(sub_problem[0], param1, param2, ...)result2 = recursion(sub_problem[1], param1, param2, ...)#递归返回值return merge_result(result1, result2)三、常见的递归题型在面试或者算法学习中，递归题型的种类繁多，下面将介绍一些常见的递归题型及其解题思路。
1. 斐波那契数列斐波那契数列是一个经典的递归问题，其定义如下：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2)斐波那契数列的递归实现非常简单，可以根据递归函数的模板直接实现：def fib(n):if n == 0:return 0if n == 1:return 1return fib(n-1) + fib(n-2)2. 汉诺塔汉诺塔问题是一个典型的递归问题，其问题描述如下：有三根柱子，第一根柱子上从下往上依次放着n 个盘子，盘子从上到下依次递增。
c语言中的递归递归是编程语言中常用的一种技术，它在C语言中也得到了广泛的应用。
递归可以理解为一种函数调用自身的方法，通过递归，我们可以简化一些问题的解决过程，提高代码的可读性和简洁性。
本文将探讨C语言中递归的基本概念、用法以及一些递归应用的实例。
一、递归的基本概念递归的本质是将原问题拆解为同类子问题，并且每个子问题的解决过程和原问题的解决过程相同。
递归函数可以通过调用自身来解决问题，每次调用的参数不断缩小，直到问题达到终止条件，递归函数开始回溯。
递归函数一般包括两个部分：基线条件和递归条件。
基线条件是递归终止的条件，递归条件是问题继续拆解的条件。
二、递归的用法递归函数在C语言中的使用非常简单。
首先，我们需要定义一个带有递归调用的函数。
在函数体内，我们需要判断基线条件，如果满足基线条件，则返回结果；如果不满足，则调用自身，并缩小参数范围，直到满足基线条件为止。
递归函数的调用过程类似于栈的操作，每次调用都将函数压入栈中，直到函数返回时再弹出栈顶元素。
三、递归的实际应用1. 阶乘函数阶乘函数是递归函数的一个典型示例。
阶乘函数可以定义为：n的阶乘等于n乘以(n-1)的阶乘。
在C语言中，可以通过递归实现阶乘函数，如下所示：```int factorial(int n) {if (n == 1) {return 1;} else {return n * factorial(n - 1);}}```2. 斐波那契数列斐波那契数列是指从0和1开始，后面的每一项都等于前面两项的和。
在C语言中，可以通过递归实现斐波那契数列的计算，如下所示：```int fibonacci(int n) {if (n == 0) {return 0;} else if (n == 1) {return 1;} else {return fibonacci(n - 1) + fibonacci(n - 2);}}```3. 文件夹遍历递归在文件夹遍历中也有广泛应用。
C语言的递归函数原理和应用场景递归是编程中一种强大而常用的技巧，尤其在C语言中，递归函数被广泛应用。
递归函数是指在函数体内调用函数本身的一种函数形式。
通过不断调用自身，递归函数能够解决一些需要重复执行的任务，使得代码更加简洁、易读、易于理解。
一、递归函数的原理递归函数的原理可以通过以下步骤来理解：1. 基本条件：递归函数中需要有一个基本条件，当满足这个条件时，递归函数将不再调用自身，结束递归。
2. 自调用：在递归函数体中，通过函数自身的调用来实现重复执行的效果。
3. 函数参数：递归函数在每次调用自身时，往往会传入不同的参数，这些参数可以决定递归的结束条件或下一次递归的运算逻辑。
4. 递归调用：递归函数在函数体内部通过调用自身来实现循环执行的效果。
二、递归函数的应用场景递归函数在编程中有许多实际应用场景，下面列举了一些常见的应用场景来说明递归函数的实用性。
1. 阶乘计算：递归函数可以非常方便地求解阶乘。
例如，对于n的阶乘可以表示为n! = n * (n-1)!，其中(n-1)!可以通过递归函数来计算。
2. 斐波那契数列：斐波那契数列是一个经典的递归问题。
数列中的每个数都是前两个数的和，即fib(n) = fib(n-1) + fib(n-2)。
通过递归函数可以很容易地计算出斐波那契数列的值。
3. 文件系统遍历：递归函数可以用来遍历文件系统中的目录结构。
通过递归调用函数来进入子目录，逐层遍历文件和文件夹，实现对整个文件系统的扫描。
4. 数据结构操作：递归函数也可以用于对各种数据结构的操作。
比如，针对树形结构的遍历、查找等操作，递归函数能够更加简洁地实现。
5. 图算法：在图算法中，递归函数常用于深度优先搜索（DFS）的实现。
通过递归调用函数，可以遍历图的各个节点，查找目标节点，或者找到所有可能的路径。
总结：递归函数是一种基于函数自身调用的编程技巧，通过重复调用自身，递归函数能够解决一些需要重复执行的任务。
递归的经典例子
1. 算数学题的时候啊，像计算一个数的阶乘，这就是一个递归的经典例子呀！比如说计算 5 的阶乘，不就是 5 乘以 4 的阶乘嘛，而 4 的阶乘又等于 4 乘以 3 的阶乘，依次类推，这多有意思啊！
2. 还有走迷宫呢，你想想，当你在迷宫里遇到岔口，你选择一条路走，然后又遇到岔口，又继续选择，这不就跟递归很像嘛！你不断地进入更小的问题去探索，直到找到出口，这难道不是很神奇吗？
3. 画树也可以用递归呀！先画一个树干，然后树干上又分出树枝，每个树枝又可以当作新的树干去继续分树枝，这不就跟递归的过程一样嘛，哇塞，这样就能画出一棵复杂又漂亮的树啦！
4. 你知道汉诺塔游戏不？那就是典型的递归例子哟！要把盘子从一个柱子移到另一个柱子，不就得不断地用递归的方法去解决嘛，天啊，真是好烧脑又好有趣！
5. 再来说说我们电脑里的文件系统，那也是递归的体现呀！文件夹里有子文件夹，子文件夹里还有子文件夹，就这么一层层下去，像不像递归在大展身手呢？
6. 回忆一下我们看电影的时候，很多故事里不是也有类似递归的情节嘛！主角解决一个问题又引出新的问题，然后一直这么循环，这也可以说是一种故事里的递归呀，多有意思的发现呀！
总之，递归在生活中无处不在，它就像一把神奇的钥匙，能打开很多复杂问题的大门，给我们带来惊喜和挑战！。
C语言递归函数递归的原理和应用场景递归函数是指在函数的定义中调用函数本身的一种方式。
通过递归函数，可以实现对问题的逐级拆分与求解，便于理解和编码。
本文将介绍C语言递归函数的原理和一些常见的应用场景。
一、递归函数的原理递归函数的原理基于分治法，将原问题不断分解为更小规模的子问题，直到满足某个递归终止条件，然后通过逐级返回求解出整个问题。
递归函数通常具有以下结构：1. 基线条件（递归终止条件）：判断是否满足递归的结束条件，当满足条件时，递归不再继续，直接返回结果。
2. 递归条件：由于递归是调用函数本身，需要满足某个条件时才执行递归调用，将问题规模缩小一步，继续求解更小规模的子问题。
3. 递归调用：在函数体内部直接调用函数本身，将问题规模不断缩小，直到满足基线条件。
二、递归函数的应用场景1. 阶乘计算：阶乘是指对于非负整数n，将其与前面所有的正整数相乘。
使用递归函数可以轻松实现阶乘的计算。
例如，计算n的阶乘可以通过函数调用factorial(n)来实现，其中factorial(n)表示计算n的阶乘。
```c#include <stdio.h>int factorial(int n) {if (n == 0 || n == 1) {return 1; // 基线条件} else {return n * factorial(n - 1); // 递归调用}}int main() {int n = 5;int result = factorial(n);printf("%d的阶乘为：%d\n", n, result);return 0;}```2. 斐波那契数列：斐波那契数列是指前两个数为1，之后的每个数都是前两个数之和。
递归函数可以简洁地实现斐波那契数列的计算。
例如，计算斐波那契数列的第n个数可以通过函数调用fibonacci(n)来实现，其中fibonacci(n)表示计算第n个斐波那契数。
生活中递归的例子递归是一种重要的编程思想，也是生活中常见的现象。
递归是指在解决问题时，将问题分解为更小的子问题，并通过递归调用自身来解决问题的过程。
在生活中，我们也可以找到很多递归的例子，下面就来列举一些。
1. 数学中的阶乘阶乘是指从1到n的所有正整数相乘的结果，用n!表示。
例如，5! = 5 × 4 × 3 × 2 × 1 = 120。
阶乘的计算可以通过递归实现，即n! = n × (n-1)!，当n=1时，(n-1)! = 1。
2. 树形结构树形结构是一种递归的数据结构，它由节点和边组成，每个节点可以有多个子节点。
树形结构的遍历也可以通过递归实现，例如先序遍历、中序遍历和后序遍历。
3. 文件夹的遍历在计算机中，文件夹也是一种树形结构，可以通过递归遍历文件夹中的所有文件和子文件夹。
例如，遍历一个文件夹中的所有文件可以通过递归实现，如果遇到子文件夹，则递归进入子文件夹进行遍历。
4. 数组的排序排序算法中的快速排序和归并排序都是基于递归实现的。
快速排序通过递归将数组分成两个子数组，然后对子数组进行排序；归并排序通过递归将数组分成两个子数组，然后将两个有序子数组合并成一个有序数组。
5. 斐波那契数列斐波那契数列是指前两个数为1，后面的每个数都是前面两个数之和的数列。
例如，1、1、2、3、5、8、13、21、34、55、89、144……斐波那契数列的计算也可以通过递归实现，即f(n) = f(n-1) + f(n-2)，当n=1或n=2时，f(n) = 1。
6. 递归函数的调用在编程中，递归函数的调用也是一种递归的过程。
当函数调用自身时，就形成了递归。
例如，计算n的阶乘可以通过递归函数实现，即factorial(n) = n * factorial(n-1)，当n=1时，factorial(n) = 1。
7. 数字的反转将一个整数的各位数字反转，可以通过递归实现。
递归的用法递归是一种编程技巧，它允许函数在其定义中调用自身。
递归的用法广泛且强大，能够解决许多复杂问题。
在理解递归的用法时，我们首先要明白其基本概念和适用场景。
递归的基本思想是将一个复杂问题分解为两个或多个相同或相似的子问题，直到子问题变得足够简单，可以直接解决。
然后，通过组合这些简单问题的解，我们可以得到原始复杂问题的解。
递归的用法在多种场合下都非常有用。
以下是一些常见的递归应用场景：阶乘计算：阶乘是递归的经典示例之一。
n的阶乘可以定义为n乘以(n-1)的阶乘，直到n为1时停止递归。
这种递归定义非常直观，并且很容易用代码实现。
斐波那契数列：斐波那契数列是另一个递归的经典示例。
每个数字是前两个数字的和，可以通过递归函数轻松计算。
树形结构遍历：在数据结构中，树形结构（如二叉树）的遍历（前序、中序、后序遍历）经常使用递归实现。
通过递归调用，我们可以轻松遍历整个树形结构。
深度优先搜索（DFS）：在图形算法中，深度优先搜索是一种常用的搜索算法，它通过递归的方式访问图形的顶点。
解析表达式：在编译器设计中，解析表达式（如算术表达式或逻辑表达式）通常使用递归实现。
通过递归调用，我们可以轻松地解析复杂的嵌套表达式。
除了以上几个例子外，递归还在许多其他领域得到应用，如动态规划、分治算法等。
然而，需要注意的是，递归虽然强大，但也可能导致性能问题，特别是在处理大规模数据时。
因此，在使用递归时，我们需要仔细考虑其适用性和性能影响。
总之，递归是一种非常有用的编程技巧，能够解决许多复杂问题。
通过理解递归的基本思想和适用场景，我们可以更好地利用这一工具，编写出更高效、更简洁的代码。
