递归算法至少要定义哪两个条件?

2023年2月21日09:35:10递归算法至少要定义哪两个条件?已关闭评论

递归是一种很特殊的算法,分治法和递归法很像一对孪生兄弟,都是将一个复杂的算法问题进行分解,让规模越来越小,最终使子问题容易求解。递归在早期人工智能所用的语言(如Lisp、Prolog)中,几乎是整个语言运行的核心,现在许多程序设计语言(包括C#、C、C++、Java、Python等)都具备递归功能。简单来说,对程序设计人员而言,“函数”(或称为子程序)不单纯是能够被其他函数调用(或引用)的程序单元,在某些程序设计语言中还提供了自己调用自己的功能,这种调用的功能就是所谓的“递归”。

从程序设计语言的角度,谈到递归的正式定义,我们可以这样描述:假如一个函数或子程序是由自身所定义或调用的,就称为递归。

递归至少要定义两个条件:

①包括一个可以反复执行的递归过程。

②一个跳出递归过程的出口。

提示

“尾递归”(Tail Recursion)就是函数或子程序的最后一条语句为递归调用,因为每次调用后,再返回前一次调用处继续执行的第一条语句就是return语句,所以不需要再进行任何运算工作了。

阶乘函数是数学上很有名的函数,对递归法而言,也可以看成是很典型的范例,我们一般以符号“!”来代表阶乘。例如4的阶乘可写为4!,n!则表示为:


n!=n*(n-1)*(n-2)*…*1

我们可以逐步分解它的运算过程,以观察其规律性:


5! = (5 * 4!)
= 5 * (4 * 3!)
= 5 * 4 * (3 * 2!)
= 5 * 4 * 3 * (2 * 1)
= 5 * 4 * (3 * 2)
= 5 * (4 * 6)
= (5 * 24)
= 120

从上述过程中,我们可以发现阶乘问题非常适合以递归法与堆栈来解决。因为它满足了递归的两大特性:

①反复执行的递归过程,②跳出递归过程的出口。

  • 版权声明:本篇文章(包括图片)来自网络,由程序自动采集,著作权(版权)归原作者所有,如有侵权联系我们删除,联系方式(QQ:452038415)。