龙空技术网

C语言:数据结构-栈与递归

Master编程树&Linux云计算 332

前言:

现时小伙伴们对“递归算法的实现原则”大概比较珍视,我们都想要知道一些“递归算法的实现原则”的相关文章。那么小编同时在网摘上搜集了一些有关“递归算法的实现原则””的相关知识,希望姐妹们能喜欢,你们一起来了解一下吧!

栈的一个重要应用是在程序设计语言中实现递归。所谓递归,是指如果一个对象部分地包括它自己,或用它自己给自己定义,则称这个对象是递归的,或定义为在一个过程中直接或间接地调用自己,则称这个过程是递归的。在调用一个函数(程序)的过程中又直接或间接地调用该函数(程序)本身,称为函数的递归调用。一个递归的求解问题必然包含终止递归的条件,当满足一定条件时就终止向下递归,从而使问题得到解决。描述递归调用过程的算法称为递归算法。在递归算法中,需要根据递归条件直接或间接地调用算法本身,当满足终止条件时结束递归调用。

现实中有许多实际问题采用递归方法来解决,使用递归的方法编写程序将使许多复杂的问题大大简化。例如计算求n的阶乘问题,可以利用阶乘的递推公式n!=n*(n-1)!,对该问题进行分解,把计算n的阶乘问题化为等式右边涉及规模较小的同类问题(n-1)的阶乘的计算。

例 用递归函数求解正整数n的阶乘(n!)

设f(n)=n!,则递归函数f(n)可表示为:

此处n=0为递归终止条件,使函数返回1;当n>0时实现递归调用,由n的值乘以f(n-1)的返回值求出f(n)的值。

上述递归函数用c语言描述为:

	int f(int n)	{	 if(n==0) return 1;	 else return n*f(n-1);	}

可见,递归算法设计的原则是用自身的简单情况来定义自身,使其一步比一步更简单,直至终止条件。设计递归算法的方法是:

(1)寻找递归的通式,将规模较大的原问题分解为规模较小、但具有类似于原问题特性的子问题。即较大的问题递归地用较小的子问题来描述,解原问题的方法同样可用来解这些子问题(例如n!=n*(n-1)!)。

(2)设置递归出口,确定递归终止条件(例如求解n!时,当n=0时,f(0)=1)。

上述求阶乘的递归函数中,假设n=4,递归函数f(4)的调用和返回过程如图3-4所示。

求解f(4)的过程

从图3-4可知,求解f(4)的值分为递归和返回求解两个阶段,在递归阶段,每一次调用f(n)函数时,并不是立即得到f(n)的值,而是一次一次地进行递归调用,即求f(4)需递归调用f(3),而f(3)无法求得,进而需要调用f(2),依次类推,直到f(0)有确定值时,递归不再进行,然后开始返回求解阶段。递归终止时,f(0)=1,由此可求出1*f(0)=1为f(1)的返回值,再由f(1)的值求出2*f(1)=2*1=2,作为f(2)的返回值。依次返回求解,最后递推出f(4)=24。

递归函数调用时,是按照“后调用先返回”的原则处理调用过程,如上述求阶乘的递归函数调用,最后调用的是f(0),因而最先返回f(0)的值。因此执行递归函数是通过具有后进先出性质的栈来实现的。系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时就为它在栈顶分配一个存储空间,而每当从一个函数退出时,就释放它的存储区。

标签: #递归算法的实现原则