ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 Excel转在线管理系统,怎么做看这里 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 EH云课堂直播课程免费学 打造核心竞争力的职场宝典
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 41192|回复: 81

递归(基础教程)

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2007-1-23 14:04 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:递归

递归是推理和问题求解的一种强有力方法,原因在于许多对象,特别是数学研究对象具有递归的结构。简单地说,如果通过一个对象自身的结构来描述或部分描述该对象就称为递归。最简单而易于理解的一个例子是阶乘的递归定义。如果以函数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(n1)

    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编辑过]

评分

参与人数 1鲜花 +2 收起 理由
autumnalRain + 2 优秀作品

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-1-23 14:05 | 显示全部楼层

再看斐波那契数列一例。

公元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(n1)+Fibo(n2)

    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(n1)+Fibo(n2)

    End If

End Function

点评

最简代码只需一句: If n > 2 Then Fibo = Fibo(n - 1) + Fibo(n - 2) Else If n Then Fibo = 1  发表于 2015-3-17 08:51

评分

参与人数 1鲜花 +2 收起 理由
高山雪原 + 2 优秀作品

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-1-23 14:07 | 显示全部楼层

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

传说印度的主神梵天做了一个塔,它在一个黄铜板上插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子过程。

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-1-23 14:08 | 显示全部楼层

 

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      '把金片nA移动到C

    Else

        Hanoi n1, A, C, B             'n?1个金片从AB,以C为过渡

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

        Hanoi n1, B, A, C             'n?1个金片从BC,以A为过渡

    End If

End Sub

TA的精华主题

TA的得分主题

发表于 2007-1-23 14:58 | 显示全部楼层

谢谢了![em27]

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

TA的精华主题

TA的得分主题

发表于 2007-1-23 16:30 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2007-1-24 08:30 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2007-1-24 09:21 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2007-1-25 11:17 | 显示全部楼层

实例(递归法求一组数(1,2~20)等于某值(100)的所有组合)


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, 下载次数: 509)

SdIIVLkW.rar

10.44 KB, 下载次数: 379

分享:递归的应用

mMpHe2H0.rar

11.44 KB, 下载次数: 328

实例(递归法求一组数(1,2~20)等于某值(100)的所有组合)

3ElMB8xT.rar

11.62 KB, 下载次数: 304

实例(递归法求一组数(1,2~20)等于某值(100)的所有组合)

lb4aGXbg.rar

11.59 KB, 下载次数: 352

实例(递归法求一组数(1,2~20)等于某值(100)的所有组合)

评分

参与人数 1鲜花 +2 收起 理由
纳铭m + 2 有实例

查看全部评分

TA的精华主题

TA的得分主题

发表于 2007-1-25 14:45 | 显示全部楼层
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,高效办公专列,每天发车

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2019-10-21 11:04 , Processed in 0.093032 second(s), 21 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表