递归

递归就是一个函数直接或间接的调用自身。一般来说,递归需要有边界条件递归前进段递归返回段,当边界条件不满足时,递归前进;边界条件满足时,递归返回。使用递归时,需要注意以下两点:

下面是使用线性递归实现斐波那契数列的例子(Lua版):

local function fibo(n)
    if n < 2 then return n end 
    return fibo(n-1) + fibo(n-2)
end

print(fibo(6))

辅助递归算法设计的工具

为了帮助我们思考和表述递归算法的思路,使算法更直观和清晰,我们定义两个节点:或节点与节点

或节点

or-node.png

A为或节点,A依不同条件会有两种不同的取值,B或C。或节点用空心圆表示。
如果多于两种取值,可用如下图表示:

2-or-node.png

与节点

and-node.png

A为与节点,A的最终取值是C节点的值,但为了求得C的值,得先求得B节点的值,C是B的函数。
与节点可能有多个相关联的点,这时可描述为下图:

2-and-node.png

A的最终取值是D节点的值,但是为了求得D的值,得先求B节点和C节点的值。从图上看得先求左边的节点的值,才能求最右边的节点的值。我们约定最右边D节点的值就是A节点的值。


什么样的程序是递归程序

试编写一个函数fact(n),求解n!。
n! = n * (n-1)!

Lua线性递归实现:

local function fact(n)
    return n == 1 and 1 or n * fact(n-1)
end

print(fact(3))

下面是fact(3)的调用和返回的递归示意图:

fact-3.png

以n=3为例,与或节点图如下:

n-equals-3-example.png

fact(n)的与或图如下:

fact-n-and-or.png

A为或节点,B为直接可解节点,值为1。C为与节点,当n>1时,A的值即为C的值,而C的值即为E的值,为了求得E的值,需要先求出D的值,E是D的函数:E = D * n,也就是E的值等于D的值fact(n-1)乘以n。

递归算法的出发点不在初始条件(递归边界)上,而是在求解目标上,也就是从所求的未知项出发,逐次调用本身,直至递归边界(初始条件)的求解过程。
递归算法比较符合人的思维方式,逻辑性强,可将问题描述的简单扼要,可读性强,易于理解。许多看起来相当复杂、难以下手的问题,如果能够使用递归算法,就会变得易于处理。


递归算法举例 - 快速排序

快速排序的基本思想:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

函数sort接受两个参数(z和y),分别表示数组中一个片段的起始与终止下标值。

quicksort.png

A是或节点,当z >= y时,A的值是B节点的值,B是直接可解节点(递归边界);当z < y时,A的值是C节点的值,C节点是与节点,C节点的值就是F节点的值,要想求得F,需要先求D、E的值,F是D、E的函数:sort(z, m-1);sort(m+1, y)。
需要特别注意的是:分区处理过程。

下面是快速排序算法的Lua实现:

local function partition(arr, s, e)
    local base, pos = arr[s], s
    for ind=s+1, e do
        if arr[ind] < base then 
            arr[pos] = arr[ind]
            --move arr[pos+1 ... ind-1] -> arr[pos+2 ... ind]
            local j = ind 
            while j > pos + 1 do
                arr[j] = arr[j-1]
                j = j - 1 
            end 
            pos = pos + 1 
            arr[pos] = base
        end 
    end 
    return pos, arr 
end

local function quicksort(arr, s, e)
    local s, e = s or 1, e or #arr
    if s >= e then return end 
    local pos = partition(arr, s, e)
    quicksort(arr, s, pos-1)
    quicksort(arr, pos+1, e)
end

递归算法举例-汉诺塔问题

hanoi.png

汉诺塔问题的与或图:

hanoi-and-or.png

其中move(n, A, B, C)的含义是:将n个盘子从A借助B搬到C。
下面是汉诺塔问题的Lua实现:

local function hanoi(n, A, B, C)
    if n <= 0 then return end 
    hanoi(n-1, A, C, B)
    print(string.format("move #%s from %s to %s.", n, A, C)) 
    hanoi(n-1, B, A, C)
end

尾递归

local function facttail(n, result)
    return n == 1 and (result or 1) or facttail(n-1, n*(result or 1)) 
end

参考文档