第三章 递归

• 递归算法的结构清晰，可读性强。但是运行时效率低下，不论是耗费的时间还是空间都比非递归算法多。
• 递归式子常分为两部分：边界条件、递归方程（最小子问题）。

常见的递归数学模型

n的阶乘Factorial

Factorial

输入：正整数n。

输出：n的阶乘结果。

if n = 0 then return 1
return n * Factorial(n-1)

• 阶乘函数可以定义为：

  逐层调用逐层返回。

斐波那契数列Fibonacci

Fibonacci

输入：正整数n。

输出：第n个斐波那契数。

if (n <= 1) then return 1
return Fibonacci(n-1) + Fibonacci(n-2)

搜索排序的递归算法

二分搜索（递归）BinarySearch

BinarySearch(A, x, low, high)

输入：n个元素的升序数组A[1···n]和元素x。

输出：如果x=A[j],1 j n，则输出j，否则输出0。

if (low <= high)
    mid = (low + high) / 2
    if (x = A[mid]) then return mid
    if (x > A[mid]) then return BinarySearch(A, x, mid+1, high)
    else return BinarySearch(A, x, low, mid-1)
    end if
else return 0
end if

• 时间复杂度：

  

  

选择排序（递归）SelectionSort

SelectionSort(1)

输入：n个元素的数组A[1···n]。

输出：按非降序排序的数组A[1···n]。

过程： sort(i) #对A[i···n]排序
if i < n then
    k <- i
    for j <- i+1 to n
        if A[j] < A[k] then k <- j
    end for
    if k != i then swap(A[i], A[k])
    sort(i+1)
end if

• 时间复杂度为

  

  

插入排序（递归）InsertionSort

InsertionSort(n)

输入：n个元素的数组A[1···n]。

输出：按非降序排序的数组A[1···n]。

过程：sort(i) #对A[1···i]进行排序
if i > 1 then
    x <- A[i]
    sort(i-1)
    j <- i - 1
    while j > 0 and A[j] > x
        A[j+1] <- A[j]
        j <- j - 1
    end while
    A[j+1] <- x
end if

生成排列

• 对数生成所有的排列组合，易知排列组合数为。例如。

算法一PERMUTATIONS1

PERMUTATIONS1

输入：正整数n。

输出：数1，2，···，n的所有可能排列。

for j <- 1 to n
    P[j] <- j
end for
prem1(1)

过程 perm1(m)
if m = n then output P[1···n]
else 
    for j <- m to n
        swap(P[j], P[m]) 
        perm1(m+1)
        swap(P[j], P[m]) #在每次perm1后要还原，以免重复
    end for
end if

• PERMUTATIONS1算法的序列输出过程如下（以为例子）：

  

• 因为排列组合数为，所以第一步共执行次；对于循环，时，执行次数为0；当时，，执行次再加上执行次数。

  

  令，则

  

  所以算法的运行时间由决定，为。

算法二PERMUTATIONS2

PERMUTATIONS1

输入：正整数n。

输出：数1，2，···，n的所有可能排列。

for j <- 1 to n
    P[j] <- 0
end for
perm2(n)

过程 perm2(m)
if m = 0 then output P[1···n]
else
    for j <- 1 to n
        if P[j] = 0 then
            P[j] <- m
            perm2(m-1)
            P[j] <- 0
        end if
    end for
end if

• PERMUTATIONS1算法的序列输出过程如下（以为例子）：

  

• PERMUTATIONS2算法的时间复杂度亦为。