递归算法

递归算法向非递归算法转换递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。

对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。

因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。

将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。

前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。

1. 直接转换法直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。

尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。

例如求阶乘的递归算法：long fact(int n){if (n==0) return 1;else return n*fact(n-1);}当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。

对于尾递归形式的递归算法，可以利用循环结构来替代。

例如求阶乘的递归算法可以写成如下循环结构的非递归算法：long fact(int n){int s=0;for (int i=1; i<=n;i++)s=s*i; //用s保存中间结果return s;}单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。

显然，尾递归是单向递归的特例。

例如求斐波那契数列的递归算法如下：int f(int n){if (n= =1 | | n= =0) return 1;else return f(n-1)+f(n-2);}对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。

数据结构论文——递归算法的讨论所谓递归算法是把问题转化为规模缩小了的同类问题的子问题。

然后递归调用函数（或过程）来表示问题的解。

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。

递归过程一般通过函数或子过程来实现。

递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。

递归算法是一种直接或者间接地调用自身算法的过程。

在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

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

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

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

所以一般不提倡用递归算法设计程序。

下面就让我们结合例子详细讨论一下递归算法。

一、递归算法的原理递归算法简单的说就是在函数中调用函数自身，不断调用，直到满足函数得出计算结果(某个条件)。

因为其需要不断循环的调用自身，所以称为递归调用。

递归的原理,其实就是一个栈(stack), 比如求5的阶乘,要知道5的阶乘,就要知道4的阶乘,4又要是到3的,以此类推,所以递归式就先把5的阶乘表示入栈, 在把4的入栈,直到最后一个,之后呢在从1开始出栈, 看起来很麻烦,确实很麻烦,他的好处就是写起代码来,十分的快,而且代码简洁,其他就没什么好处了,运行效率出奇的慢。

还有一个十分形象的例子：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事……如此循环往复到最终的要求。

递归分为2种，直接递归和间接递归。

直接递归，比如方法A内部调用方法A自身。

间接递归，比如方法A内部调用方法B，方法B内部调用方法C，方法C 内部调用方法A。

递归算法详解完整版递归算法是一种重要的算法思想，在问题解决中起到了很大的作用。

它通过将一个大问题划分为相同或类似的小问题，并将小问题的解合并起来从而得到大问题的解。

下面我们将详细介绍递归算法的定义、基本原理以及其应用。

首先，我们来定义递归算法。

递归算法是一种通过调用自身解决问题的算法。

它通常包括两个部分：基础案例和递归步骤。

基础案例是指问题可以被直接解决的边界情况，而递归步骤是指将大问题划分为较小问题并通过递归调用自身解决。

递归算法的基本原理是"自顶向下"的思维方式。

即从大问题出发，不断将问题划分为较小的子问题，并解决子问题，直到达到基础案例。

然后将子问题的解合并起来，得到原始问题的解。

递归算法的最大特点是简洁而优雅。

通过将复杂问题分解为简单问题的解决方式，可以大大减少代码的复杂程度，提高程序的效率和可读性。

但是递归算法也有一些缺点，包括递归深度的限制和复杂度的不确定性。

过深的递归调用可能导致栈溢出，而不合理的递归步骤可能导致复杂度过高。

递归算法有许多应用场景，我们来介绍其中一些典型的应用。

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.二叉树问题：对于给定的二叉树，递归算法可以通过递归调用左子树和右子树的解来解决。

6种基本算法递归递归是一种重要的算法思想，它在计算机科学中得到广泛应用。

本文将介绍六种基本的递归算法，并对其原理和应用进行讲解。

一、递归的基本概念递归是指一个函数在其定义中调用自身的过程。

递归算法通过将一个大问题划分为一个或多个相同或相似的子问题，然后通过解决子问题来解决原始问题。

递归算法具有简洁、优雅以及可读性强的特点，但同时也需要注意递归的停止条件，以避免无限递归的发生。

二、阶乘算法阶乘算法是递归算法中最经典的例子之一。

它的定义如下：```n! = n * (n-1) * (n-2) * ... * 1```其中，n为一个非负整数。

阶乘算法可以通过递归的方式实现，即：```fact(n) = n * fact(n-1)```其中，停止条件为`n=0`时，返回1。

三、斐波那契数列算法斐波那契数列是一个无限序列，其定义如下：```F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) (n>1)```斐波那契数列算法可以通过递归的方式实现，即：```fib(n) = fib(n-1) + fib(n-2)```其中，停止条件为`n=0`或`n=1`时，返回相应的值。

四、二分查找算法二分查找算法是一种高效的查找算法，它的基本原理是将已排序的数组分成两部分，然后判断目标值在哪一部分，并继续在该部分中进行查找，直到找到目标值或者查找范围为空。

二分查找算法可以通过递归的方式实现，即：```binarySearch(arr, target, start, end) = binarySearch(arr, target, start, mid-1) (target < arr[mid])= binarySearch(arr, target, mid+1, end) (target > arr[mid])= mid (target = arr[mid])```其中，`arr`为已排序的数组，`target`为目标值，`start`和`end`为查找范围的起始和结束位置。

排列组合递归算法是一种基于递归思想的算法，用于解决与排列和组合相关的问题。

下面是排列组合递归算法的详细介绍：
基本概念：
排列（Permutation）：从n个不同元素中取出m（m ≤n）个不同元素按照一定的顺序排成一列，称为从n个元素中取出m个元素的一个排列，所有排列的个数记为P(n,m)。

组合（Combination）：从n个不同元素中取出m（m ≤n）个不同元素按照一定的顺序排成一列，不考虑排列的顺序，称为从n个元素中取出m个元素的一个组合，所有组合的个数记为C(n,m)。

递归的基本思想：
递归算法的基本思想是将一个复杂的问题分解为若干个简单的问题，然后将这些简单问题的解组合起来得到原问题的解。

在排列组合问题中，可以将一个大问题分解为若干个小问题，例如：从n个元素中取出m个元素的排列/组合问题可以分解为从剩余元素中继续取下一个元素的问题。

递归公式：
排列的递归公式：P(n,m) = n * P(n-1,m-1) + P(n-1,m)
组合的递归公式：C(n,m) = P(n,m) / P(m,m) = (n * P(n-1,m-1) + P(n-1,m)) / P(m,m)
应用示例：
使用排列组合递归算法可以解决很多与排列和组合相关的问题，例如：给定一个数组，求数组中所有元素的排列/组合数、给定一个集合，求集合的所有子集等。

注意事项：
在使用递归算法时需要注意避免出现无限递归的情况，需要对递归终止条件进行正确的设置。

另外，由于递归算法会涉及到大量的重复计算，因此在处理大规模数据时可能会效率较低，可以考虑使用动态规划等优化方法来提高算法的效率。

前言说白了递归就象我们讲的那个故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：……也就是直接或间接地调用了其自身。

就象上面的故事那样，故事中包含了故事本身。

因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。

函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。

对于代码中功能性较强的、重复执行的或经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。

例如我们把上面的讲故事的过程包装成一个函数，就会得到：void Story(){puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：");getchar();//按任意键听下一个故事的内容Story(); //老和尚讲的故事，实际上就是上面那个故事}函数的功能是输出这个故事的内容，等用户按任意键后，重复的输出这段内容。

我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。

出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来，正如我们听了几遍相同的故事后会大叫：“够了！”。

于是我们可以得到下面的程序：#include<stdio.h>const int MAX = 3;void Story(int n);//讲故事int main(void){Story(0);getchar();return 0;}void Story(int n){if (n < MAX){puts("从前有座山，山里有座庙，庙里有个老和尚，老和尚对小和尚说了一个故事：");getchar();Story(n+1);}else{printf("都讲%d遍了！你烦不烦哪？\n", n);return ;}}上面的Story函数设计了一个参数n，用来表示函数被重复的次数，当重复次数达到人们忍受的极限（MAX次）时，便停下来。

递归算法的应用
递归算法是指在计算机科学中，一种使用自身的方法来解决一个问题的算法。

它的基本思想是将一个复杂的问题分解成一些规模较小的相同问题，将它们一一解决，然后将解决的结果合并起来，就得到原来问题的答案。

它与迭代(iteration)大体相同，不同的是迭代使用循环，而递归使用函数调用。

递归算法常用于排序和搜索算法。

例如，快速排序和归并排序就是采用递归的思想来实现的。

在游戏开发和计算机图形学等领域，也常采用递归算法。

比如大家熟悉的迷宫寻路算法就有递归实现。

此外，递归还可以用于处理树结构，如表达式树(Expression Tree)，以及图形处理中的树结构，如HTML、XML文件等。

总之，递归算法在计算机科学里被广泛使用，它使编程者可以使用少量的代码把复杂性以容易理解的形式表达出来。

它不仅可以用来解决各种规模的问题，而且在算法复杂度上也具有一定的优势。

【算法分析】递归算法的⼏个经典例⼦例⼀：整数划分问题 将正整数n表⽰成⼀系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表⽰称为正整数n的划分。

求正整数n的不同划分个数。

例如：正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加⼀个⾃变量：将最⼤加数n1不⼤于m的划分个数记作q(n,m)。

下⾯对可能出现的四种情况进⾏分析：① m=1： 当m等于1时，对n的划分只可能1+1+1+……+1这⼀种情况。

②m>n时： 当m⼤于n时，由于划分中不可能出现负数，所以{n1, n2, n2,… , nk}（n = n1+n2+n3+……+nk）只可能出现⼩于等于n的整数。

故有q(n, m)=q(n, n)⑤m=n时： 当m等于n时，包含n⾃⾝的划分和没有n的划分两个部分。

⽽包含n⾃⾝的划分只有⼀种情况，故有有q(n, n)=1+q(n,n-1)④m<n时： n的m划分有包含m和不包含m两个部分。

其中包含m的部分⽤集合可表⽰为{m, {x1, x2, x3, 4,…, xk}}(其中x1+x2+……+xk=n-m)【详解见图1】，这部分的划分数为q(n-m, m)；⽽不包含m的划分中，最⼤值不能为m，故划分数就等于q(n, m)。

所以在m<n时整数n的划分数为：q(n, m)=q(n, m-1)+q(n-m, m)。

【图1：ipad坏了，⼀时找不到纸，后⾯再补吧。

】递归求整数划分：1int q(int n, int m){2if(m==1){3return1;4 }5else if(m>n){6return q(n,n);7 }8else if(m==n){9return q(n,n-1)+1;10 }11else if(m<n){12return q(n-m, m)+q(n,m-1);13 }14 }。

递归算法和递推算法的原理-概述说明以及解释1.引言1.1 概述递归算法和递推算法是编程中常用的两种算法思想，它们都是一种问题解决的方法论。

递归算法通过将一个大问题分解为一个或多个相同的小问题来解决，而递推算法则是通过给定初始条件，通过逐步推导出后续结果来解决问题。

递归算法是一种自调用的算法，它将一个问题划分为更小规模的相同子问题，并通过调用自身来解决这些子问题。

每个子问题的解决方案被合并以形成原始问题的解决方案。

递归算法具有简洁的代码结构和易于理解的逻辑。

它在一些问题上能够提供高效的解决方案，例如树的遍历、图的搜索等。

递推算法则是从已知的初始条件开始，通过根据给定的递推公式或规则，逐步计算出后续的结果。

递推算法是一种迭代的过程，每一次迭代都会根据已知条件计算得出下一个结果。

递推算法常应用于数学问题，求解斐波那契数列、阶乘等等。

递归算法和递推算法在解决问题时的思路不同，但也存在一些相似之处。

它们都能够将大问题分解成小问题，并通过解决这些子问题来获得问题的解决方案。

而且递归算法和递推算法都有各自适用的场景和优缺点。

本文将详细介绍递归算法和递推算法的原理、应用场景以及它们的优缺点。

通过比较和分析两者的差异，帮助读者理解和选择合适的算法思想来解决问题。

1.2文章结构文章结构部分的内容可以描述文章的整体框架和各个章节的内容概要。

根据给出的目录，可以编写如下内容：文章结构：本文主要探讨递归算法和递推算法的原理及其应用场景，并对两者进行比较和结论。

文章分为四个部分，下面将对各章节的内容进行概要介绍。

第一部分：引言在引言部分，我们将对递归算法和递推算法进行简要概述，并介绍本文的结构和目的。

进一步，我们将总结递归算法和递推算法在实际问题中的应用和重要性。

第二部分：递归算法的原理在第二部分，我们将详细讨论递归算法的原理。

首先，我们会给出递归的定义和特点，探索递归的本质以及递归算法的基本原理。

其次，我们将展示递归算法在不同的应用场景中的灵活性和效果。

递归算法的优缺点简介在计算机科学中，递归是一种通过将问题分解为更小的子问题来解决问题的方法。

递归算法通过反复调用函数本身来实现。

它在许多计算机科学和编程领域中都有广泛的应用，例如数据结构、算法和编程语言等。

虽然递归算法可以简化问题的解决过程，但也有其特定的优点和局限性。

优点1. 简洁性递归算法的一大优点是其简洁性。

递归算法可以通过将问题分解为更小的子问题来解决复杂的问题。

相比于使用迭代循环或其他复杂的算法，递归算法通常更容易理解和实现。

通过使用递归，我们可以将复杂的问题转化为简单的步骤，从而更容易思考和编写代码。

2. 可读性递归算法通常具有良好的可读性。

递归函数将问题分解为更小的子问题，这使得代码更易于理解和调试。

相比之下，使用迭代或其他复杂算法的代码可能更难理解和维护。

递归算法的可读性是其优点之一，尤其是对于解决复杂问题时。

3. 可重用性递归算法具有良好的可重用性。

一旦我们编写了一个递归函数来解决特定问题，我们可以轻松地在其他地方重用它。

递归函数可以作为一个独立的模块，可以在不同的上下文中使用，从而提高代码的可重用性。

4. 代码简洁在某些情况下，递归算法可以使代码更加简洁。

递归算法通常使用较少的代码行数来实现同样的功能。

相比于使用循环和迭代，递归算法更容易编写和维护。

这不仅可以节省时间，还可以减少代码的复杂性和出错的可能性。

缺点1. 内存消耗递归算法的一个主要缺点是内存消耗问题。

每次递归调用函数时，系统都需要为其分配内存空间来保存函数的局部变量和上下文信息。

随着递归的深度增加，内存使用也会不断增加。

在处理大量数据或深度递归的情况下，内存消耗可能会成为一个重要的问题。

2. 执行效率递归算法的执行效率通常较低。

与迭代算法相比，递归算法具有更多的函数调用和返回操作。

这些额外的开销会影响程序的运行效率。

特别是对于大规模的问题和递归层次较深的问题，递归算法的执行效率可能明显降低。

3. 栈溢出递归算法容易导致栈溢出。