递归（基础教程）

彭希仁

递归是推理和问题求解的一种强有力方法，原因在于许多对象，特别是数学研究对象具有递归的结构。简单地说，如果通过一个对象自身的结构来描述或部分描述该对象就称为递归。最简单而易于理解的一个例子是阶乘的递归定义。如果以函数f(n)表示自然数n的阶乘的值，则有定义：

                              

递归定义使我们能够用有限的语句描述一个无穷的集合。本例描述一个无穷的集合只用了两个语句。

VB程序设计语言允许一个过程体中有调用自身的语句，称为递归调用。也允许调用另一过程，而该过程又反过来调用本过程，称为间接递归调用。这种功能为求解具有递归结构的问题提供了强有力手段，使程序语言的描述与问题的自然描述完全一致，因而使程序易于理解、易于保证和维护。例如，对于上面的n阶乘的递归定义，可以写出相应的VB函数过程，如下面的例8.24。这个过程的推理（计算）路线与原来函数的（递归）数学定义完全一致。

例8.24  求n阶乘的VB函数过程。

Private Function F( byval n As Integer ) As long

    If n=1 Then

        F=1

    Else:

        F=n*F(n－1)

    End If

End Function

让我们来跟踪这个程序的计算过程，令n=4调用这个函数，用下面的形式来表示递归求解的过程：

（1）F(4)=4×F(3)      'n=4调用函数过程F(3)

（2）F(3)=3×F(2)      'n=3调用函数过程F(2)

（3）F(2)=2×F(1)      'n=2调用函数过程F(1)

（4）F(1)=1             'n=1求得F(1)的值

（5）F(2)=2×1=2       '回归，n=2,求得F(2)的值

（6）F(3)=3×2=6       '回归，n=3,求得F(3)的值

（7）F(4)=4×6=24      '回归，n=4,求得F(4)的值

上面第一步到第四步求出F(1)=1的步骤称为递推，从第四步到第七步求出F(4)=4×6的步骤称为回归。

从这个例子可以看出，递归求解有两个条件：

1．给出递归终止的条件和相应的状态。

在本例中递归终止的条件是n=1，状态是F(1)=1。

2．给出递归的表述形式，并且这种表述要向着终止条件变化，在有限步内达到终止条件。

在本例中，当n>1时，给出递归的表述形式为 F(n)=n×F(n－1)，函数值F(n)用函数值F(n－1)来表示。参数的值向减少的方向变化，在第n步出现终止条件n=1。

[此贴子已经被作者于2007-1-26 9:34:25编辑过]

彭希仁

再看斐波那契数列一例。

公元1202年欧洲数学家伦纳德·斐波那契在他所著的《珠算的书》（Liber Abbaci）中有这样一道习题：假定每对兔子每个月生出一对兔子。新生的兔子一个月后有了生育能力，再过一个月又生出一对兔子。那么买一对新生的兔子回来，一年后有多少对兔子？

显然，第一个月有一对，第二个月还是一对，第三个月有两对，第四个月有三对，第五个月有五对……容易推得，某月的兔子数正好是前两个月兔子数之和。如果用F(n)表示第n个月的兔子数，则当n>2时有：

F(n)=F(n－1)+F(n－2)     n≥3

F(1)=F(2)=1

若定义F(0)=0，则可以写成：

F(n)=F(n－1)+F(n－2)    n≥2

F(0)=0,F(1)=1

这个数列称为斐波那契数列。上面的表达式是该数列的递归定义，其终止条件是n=0和n=1,递归形式是F(n)=F(n－1)+F(n－2)。即当n≥2时，函数F(n)用它本身在自变量较小的两个点处的值来(递归)表示，这个递归表示向着终止条件(n=0,n=1)变化,所以这个问题可以递归求解。可以写一个VB的函数过程来计算第n个斐波那契数。

 

例8.25  求第n个斐波那契数。

Private Function Fibo(ByVal n As Integer) As Integer

                    '函数的返回值为第n个斐波那契数

    If (n=0) Then

        Fibo=0

    ElseIf n=1 Then

        Fibo=1

    Else: Fibo=Fibo(n－1)+Fibo(n－2)

    End If

End Function

例8.25  求第n个斐波那契数。

Private Function Fibo(ByVal n As Integer) As Integer

                    '函数的返回值为第n个斐波那契数

    If (n=0) Then

        Fibo=0

    ElseIf n=1 Then

        Fibo=1

    Else: Fibo=Fibo(n－1)+Fibo(n－2)

    End If

End Function

彭希仁

再看一个非数值的例子——汉诺塔。

传说印度的主神梵天做了一个塔，它在一个黄铜板上插3根宝石针，其中一根针上从上到下按从小到大的顺序串上了64个金片。梵天要求僧侣们把金片全部移动到另一根针上去，规定每次只能移动一片，且不许将大片压在小片上。并说如果这64片金片全部移至另一根针上时，世界就会在一声霹雳之中毁灭。

僧侣们怎样完成梵天交给他们的任务呢？为了便于说明，把问题用精确的语言加以表述。称搬动n个金片的问题为n阶汉诺塔问题。以A，B，C代表3根宝石针，把金片从小到大编号为1至n，引入记号：

Move(n,A,B,C)—— n个金片从A移到C，以B为过渡(n阶汉诺塔问题)。

显然，一阶汉诺塔问题M(1,A,B,C)即把一个金片直接从A移到C， 是一个立刻可以直接解决的问题。解决这类问题通常采用所谓降阶法。

注意到，为了把n片金片从A移到C，必须把最大的金片n从A移到C。为此，首先要把金片1～（n－1）搬到B针上，金片n搬到C后就再也不必移动了。剩下的问题是把（n－1）片金片从B移到C（以A为过渡）。于是，求解n阶汉诺塔问题变成了求解两个（n－1）阶汉诺塔问题，问题降了一阶。而一阶汉诺塔问题是立刻可以解决的问题。由此可以看到，这是一个典型的递归问题，问题可表述为：

为了解决n阶汉诺塔问题Move(n,A,B,C)，可以依次解决（n－1）阶汉诺塔问题Move(n－1,A,C,B)、1阶汉诺塔问题M(1，A,B,C)和（n－1）阶汉诺塔问题Move(n－1,B,A,C)。即n阶汉诺塔问题可以用（n－1）阶汉诺塔问题来表述,这种方法称为降阶。

递归终止条件为n=1，遵循降阶的步骤,经过有限步后必定能达到n=1。这样就可以使用递归过程来求解此问题了。

下面是求解n阶汉诺塔问题的VB子过程。

彭希仁

 

例8.26  汉诺塔。

Private Sub Hanoi(ByVal n%, ByVal A$, ByVal B$, ByVal C$)

                      '在本例子过程中,在窗体上打印 “A → C” 来代表把金片从A针移动

                      '到C针,即1阶汉诺塔问题的解

    If n=1 Then

        Print n; ": "; A; "→"; C      '把金片n从A移动到C

    Else

        Hanoi n－1, A, C, B             'n?1个金片从A到B，以C为过渡

        Print n; ": "; A; "→ "; C     '把金片n从A移动到C

        Hanoi n－1, B, A, C             'n?1个金片从B到C，以A为过渡

    End If

End Sub

Long_III

谢谢了！[em27]

收藏先，也建议楼主给出一些与excel联系的例子做示例

northwolves

谢谢分享

fanrong88

谢谢分享

shiju8_szb

谢谢先学习一下

彭希仁

Public arr1, j As Long, z%, k%
Public arr3(1 To 65536, 1 To 1) As String
Sub peng()
    Application.ScreenUpdating = False
    aa = Timer
    j = 0
    z = [A65536].End(xlUp).Row     '查找A列最后一行
    arr1 = Range("a1", Cells(z, 1))  '导入数组
    k = Cells(1, 2)   '需要去等于的值
    xi 1, 0, ""
    Range(Cells(1, 3), Cells(j, 3)) = arr3
    MsgBox "找到 " & j & " 个解! 花费" & Format(Timer - aa, "0.00") & "秒"
End Sub
Sub xi(i%, x%, y$)
    If x + arr1(i, 1) = k Then
        j = j + 1
        arr3(j, 1) = y & arr1(i, 1) & "=" & k
    End If
    If i < z And x < k Then       '
        If x + arr1(i, 1) < k Then xi i + 1, x + arr1(i, 1), y & arr1(i, 1) & "+"    '调用自已进行递归
        xi i + 1, x, y       '调用自已进行递归
    End If
End Sub

说明：

其实所有组合与二进制是一样的道理，如一，二，三的所有组合

000      

001     三

010     二

011    二  ， 三

100     一

101      一 ，三

110     一，二

111       一，二，三

对于数字一来说，也只有0（不出现）和1（出现） 两种情况，

当数字一出现，对于数字二来说分0（不出现）和1（出现）

当数字一不出现，对于数字二来说分0（不出现）和1（出现）

。。。。。。。

其实也就只有两种情况，我们只需把这两种情况进行递归就可以了，直到递归来最后一位终止递归。

现丑了。

YA5aw4Vz.rar (11.73 KB, 下载次数: 924)

2007-1-25 14:26 上传

点击文件名下载附件
实例（递归法求一组数（1，2～20）等于某值（100）的所有组合）

[此贴子已经被作者于2007-1-26 10:17:13编辑过]

43379677

不错学习了