递归函数简单实例 递归算法几个经典例子

大家好，今天来为大家解答递归函数简单实例这个问题的一些问题点，包括递归算法几个经典例子也一样很多人还不知道，因此呢，今天就来为大家分析分析，现在让我们一起来看看吧！如果解决了您的问题，还望您关注下本站哦，谢谢~

尾递归的实例

为了理解尾递归是如何工作的，让我们再次以递归的形式计算阶乘。首先，这可以很容易让我们理解为什么之前所定义的递归不是尾递归。回忆之前对计算n!的定义：在每个活跃期计算n倍的(n－1)!的值，让n=n－1并持续这个过程直到n=1为止。这种定义不是尾递归的，因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值，因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。现在让我们考虑以尾递归的形式来定义计算n!的过程。

这种定义还需要接受第二个参数a，除此之外并没有太大区别。a（初始化为1）维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而，在每次递归调用中，令a=na并且n=n－1。继续递归调用，直到n=1，这满足结束条件，此时直接返回a即可。

代码实例3-2给出了一个C函数facttail，它接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数a，a的初始值为1。facttail使用a来维护递归层次的深度，除此之外它和fact很相似。读者可以注意一下函数的具体实现和尾递归定义的相似之处。

示例3-2：以尾递归的形式计算阶乘的一个函数实现/*facttail.c*/#includefacttail.h/*facttail*/intfacttail(intn,inta){/*Computeafactorialinatail-recursivemanner.*/if(n<0)return0;elseif(n==0)return1;elseif(n==1)returna;elsereturnfacttail(n-1,n*a);}示例3-2中的函数是尾递归的，因为对facttail的单次递归调用是函数返回前最后执行的一条语句。在facttail中碰巧最后一条语句也是对facttail的调用，但这并不是必需的。换句话说，在递归调用之后还可以有其他的语句执行，只是它们只能在递归调用没有执行时才可以执行。尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。比如f(n, sum)= f(n-1)+ value(n)+ sum;会保存n个函数调用堆栈，而使用尾递归f(n, sum)= f(n-1, sum+value(n));这样则只保留后一个函数堆栈即可，之前的可优化删去。

也许在C语言中有很多的特例，但编程语言不只有C语言，在函数式语言Erlang中（亦是栈语言），如果想要保持语言的高并发特性，就必须用尾递归来替代传统的递归。

原文的说法是错误的：原文如下：

一种算法,用于计算机编程技术.

尾递归是针对传统的递归算法而言的,传统的递归算法在很多时候被视为洪水猛兽.它的名声狼籍,好像永远和低效联系在一起.

尾递归就是从最后开始计算,每递归一次就算出相应的结果,也就是说,函数调用出现在调用者函数的尾部,因为是尾部,所以根本没有必要去保存任何局部变量.直接让被调用的函数返回时越过调用者,返回到调用者的调用者去.

以下是具体实例:

线性递归: longRescuvie(longn){return(n==1)?1:n*Rescuvie(n-1);}尾递归: longTailRescuvie(longn,longa){return(n==1)?a:TailRescuvie(n-1,a*n);}longTailRescuvie(longn){//封装用的return(n==0)?1:TailRescuvie(n,1);}当n= 5时

对于线性递归,他的递归过程如下:

Rescuvie(5)

{5* Rescuvie(4)}

{5*{4* Rescuvie(3)}}

{5*{4*{3* Rescuvie(2)}}}

{5*{4*{3*{2* Rescuvie(1)}}}}

{5*{4*{3*{2* 1}}}}

{5*{4*{3* 2}}}

{5*{4* 6}}

{5* 24}

120

对于尾递归,他的递归过程如下:

TailRescuvie(5)

TailRescuvie(5, 1)

TailRescuvie(4, 5)

TailRescuvie(3, 20)

TailRescuvie(2, 60)

TailRescuvie(1, 120)

120

很容易看出,普通的线性递归比尾递归更加消耗资源,在实现上说,每次重复的过程

调用都使得调用链条不断加长.系统不得不使用栈进行数据保存和恢复.而尾递归就

不存在这样的问题,因为他的状态完全由n和a保存.

具体事例2快速排序算法实施尾递归优化 voidquickSort(SqList*list,intlow,inthigh){intpivot;while(low<high){pivot=Partition(list,low,high);quickSort(list,low,pivot-1);//quickSort(list,low,pivot-1);原递归调用//quickSort(list,pivot+1,high);low=pivot+1;/*尾递归*/}}//

首先：尾递归是线性递归的子集，属于线性递归。具体概念请参阅各大高校出版的书籍。作者把概念搞错了

其次，上文所举的第二个例子中在TailRescuvie(n-1, 1)没有计算出来之前，是不能return的。也就是说递归过程和第一个例子是差不多的，根本没有节约资源，甚至更浪费。

其实，编译器会很容易的对尾递归使用跳转语句进行优化，其实是可以return的。

尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题——因为参数里带有前面若干步的运算路径。对于阶乘而言，越深并不意味着越复杂。

从时间和空间效率上看，尾递归和传统递归差不多。递归运算效率低主要是分支巨大，像阶乘这类单分支的递归，效率并不低。递归运算的深度和运算总量大致成指数关系，return多次并不会造成显著的性能损失。

一言以蔽之，传统递归越深，距离目标越近；尾递归越深，距离起点越远。

尾递归适用于运算对当前递归路径有依赖的问题，传统递归适用于运算对更深层递归有依赖的问题。

/**************************************************************************************************/

第二作者对第二个例子的解释上有点不全面，尾递归的效果就是去除了将下层的结果再次返回给上层，需要上层继续计算才得出结果的弊端，如果读者仔细观看第二例子就可以看出，其实每个递归的结果是存储在第二个参数a中的，到最后一次计算的时候，会只返回一个a的值，但是因为是递归的原理虽然仍然要返回给上层，依次到顶部才给出结果，但是不需要再做计算了，这点的好处就是每次分配的内存不会因为递归而扩大。

在效率上，两者的确差不多。

python递归算法经典实例有哪些

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

Python

是完全面向对象的语言。函数、模块、数字、字符串都是对象。并且完全支持继承、重载、派生、多继承，有益于增强源代码的复用性。Python支持重载运算符和动态类型。相对于Lisp这种传统的函数式编程语言，Python对函数式设计只提供了有限的支持。有两个标准库(functools, itertools)提供了Haskell和Standard ML中久经考验的函数式程序设计工具。

递归方程 是什么

递归方程是一种数学方程，它通过定义当前项与之前项（或几项）之间的关系来定义一个序列。以下是关于递归方程的详细解释：

一、定义与特点

定义：递归方程的核心在于“递归”二字，即它使用序列中的前一项（或前几项）来定义当前项。这种定义方式使得序列的每一项都能通过已知项计算得出。特点：递归方程通常具有简洁的形式，但能够描述复杂的序列结构。例如，斐波那契数列的递归方程为F(n)= F(n-1)+ F(n-2)，其中F(n)表示斐波那契数列的第n项。二、一般形式

递归方程的一般形式可以表示为a_n= f(a_{n-1}, a_{n-2},..., a_{n-k})，其中a_n表示序列的第n项，f是一个函数，它根据序列的前k项来计算第n项。k的值取决于具体的递归方程，对于简单的递归方程，k可能等于1（如等差数列的递推公式），对于更复杂的递归方程，k可能大于1（如斐波那契数列的递归方程）。三、应用与实例

应用：递归方程在自然科学、计算机科学、经济学等多个领域都有广泛应用。例如，在计算机科学中，递归方程常用于描述分治算法的时间复杂度；在经济学中，递归方程可用于描述动态经济系统的行为。实例：斐波那契数列是递归方程的一个经典实例。它的递归方程为F(n)= F(n-1)+ F(n-2)，且初始条件为F(1)= 1，F(2)= 1。通过这个递归方程，我们可以计算出斐波那契数列的任意一项。综上所述，递归方程是一种强大的数学工具，它能够通过简洁的形式描述复杂的序列结构，并在多个领域发挥重要作用。

文章分享结束，递归函数简单实例和递归算法几个经典例子的答案你都知道了吗？欢迎再次光临本站哦！