递归是一种很特殊的算法,分治法和递归法很像一对孪生兄弟,都是将一个复杂的算法问题进行分解,让规模越来越小,最终使子问题容易求解。递归在早期人工智能所用的语言(如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
从上述过程中,我们可以发现阶乘问题非常适合以递归法与堆栈来解决。因为它满足了递归的两大特性:
①反复执行的递归过程,②跳出递归过程的出口。