ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: 彭希仁

递归(基础教程)

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2012-11-12 13:59 | 显示全部楼层
本帖已被收录到知识树中,索引项:递归
自己摸索了两个月,才终于发现宝贝,谢谢高手费心,写出如此详细的教程。{:soso_e156:}

TA的精华主题

TA的得分主题

发表于 2013-7-15 20:46 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2014-2-20 10:06 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
彭希仁 发表于 2007-1-25 11:17
Public arr1, j As Long, z%, k%Public arr3(1 To 65536, 1 To 1) As StringSub peng()     ...

  xi i + 1, x, y       '调用自已进行递归      
请教楼主这句是什么意思? 赋值?还是别的?   xi 的值在变化吗?  

TA的精华主题

TA的得分主题

发表于 2014-6-12 16:41 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
太好了,感谢楼主分享!

TA的精华主题

TA的得分主题

发表于 2014-11-13 16:22 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
彭希仁 发表于 2007-1-23 14:05
再看斐波那契数列一例。
                                公元1202年欧洲数学家伦纳德·斐波那契在他所著的《珠算的书》(Liber Abbaci ...

斐波那契数列计算到n为30的时候就开始变慢了 请问有什么解决的方案嘛~

TA的精华主题

TA的得分主题

发表于 2014-11-13 23:01 | 显示全部楼层
彭希仁 发表于 2007-1-25 11:17
Public arr1, j As Long, z%, k%Public arr3(1 To 65536, 1 To 1) As StringSub peng()     ...

好的学习资料!收藏!

TA的精华主题

TA的得分主题

发表于 2015-3-16 23:28 | 显示全部楼层
663973866 发表于 2014-11-13 16:22
斐波那契数列计算到n为30的时候就开始变慢了 请问有什么解决的方案嘛~

我的电脑上也是差不多到n=30就慢了,到n=40,已经达到6分钟。
使用循环代替递归,n=40,仅0.2秒不到。
下面是我的代码:
  1. Function fblq(n&, a)  '递归版
  2. ' Dim arr&(n)
  3.   Static a1
  4.   a1 = a1 + 1
  5.     If n <= 2 Then
  6.       fblq = 1
  7.     Else:
  8.       fblq = fblq(n - 2, a) + fblq(n - 1, a)
  9.     End If
  10.    a(0) = a1
  11. '   fblq = arr(n)
  12. End Function

  13. Sub 测试斐波拉契数列()

  14. Dim i&, r, c, tim1, tim2, a()
  15. ReDim a(1)
  16. tim1 = Timer
  17. For i = 1 To 40
  18. Cells(Int((i - 1) / 10) + 3, (i - 1) Mod 10 + 1) = fblq(i, a)
  19. Next i
  20. tim2 = Timer

  21. Cells(1, 2) = tim2 - tim1
  22. Cells(2, 2) = a(0)
  23. End Sub


  24. Function fblq2(n%, a) As Double   '循环版
  25.   Dim arr() As Double
  26.   ReDim arr(n)
  27. ' Static a1
  28. Dim i

  29.   'a1 = a1 + 1
  30.     If n <= 2 Then
  31.       arr(n) = 1
  32.     Else:
  33.       arr(1) = 1
  34.       arr(2) = 1

  35.       For i = 3 To n
  36.       a = a + 1
  37.       arr(i) = arr(i - 2) + arr(i - 1)
  38.       Next i
  39.     End If
  40.    
  41.    fblq2 = arr(n)
  42. End Function

  43. Sub 测试斐波拉契数列2()

  44. Dim i%, r, c, tim1, tim2, a


  45. tim1 = Timer
  46. For i = 1 To 40
  47. a = 0
  48. Cells(Int((i - 1) / 10) + 8, (i - 1) Mod 10 + 1) = fblq2(i, a)
  49. Cells(Int((i - 1) / 10) + 18, (i - 1) Mod 10 + 1) = a


  50. Next i


  51. tim2 = Timer

  52. Cells(1, 1) = tim2 - tim1


  53. End Sub
复制代码

TA的精华主题

TA的得分主题

发表于 2015-3-17 08:48 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 香川群子 于 2015-3-17 09:09 编辑
下标越界 发表于 2015-3-16 23:28
我的电脑上也是差不多到n=30就慢了,到n=40,已经达到6分钟。
使用循环代替递归,n=40,仅0.2秒不到。
下 ...

你的代码可以大大简化:

首先,递归的代码:
  1. Function Fibo(n%) '斐波那契数 递归计算
  2.     If n > 1 Then Fibo = Fibo(n - 1) + Fibo(n - 2) Else If n Then Fibo = 1
  3. End Function
复制代码
这是If 结构的横向写法。

如果按照If结构展开,则可以是:
    If n > 1 Then
        Fibo = Fibo(n - 1) + Fibo(n - 2)
    Else 'If n = 1 Or n = 0 Then
        If n Then Fibo = 1 'Else If n = 0 Then Fibo = 0
    End If
蓝色部分是可以省略的。

如果不省略(便于理解)则成为:
    If n > 1 Then
        Fibo = Fibo(n - 1) + Fibo(n - 2)
    ElseIf n = 1 Or n = 0 Then
        If n = 1 Then '可以省略为If n Then
            Fibo = 1
        ElseIf n = 0 Then
            Fibo = 0 '因为Fibo初始值=0所以只一句也可以省略
        End If

    End If

红色部分和蓝色部分,都是可以省略的。
实际上运行效果是完全一致的。

所以,我的递归代码最简洁,只需一句代码:
If n > 1 Then Fibo = Fibo(n - 1) + Fibo(n - 2) Else If n Then Fibo = 1

呵呵。

…………
补充解释,为什么递归计算n较大时(n>30)时会比较慢呢?

因为每一次递归过程都需要递减到n=1和n=0时才能结束,
例如,n=30时,
总的递归次数达到了: 2,692,537次,
其中n=1 递归了:832,040次,
n=0 递归了:514,229次

所以,计算速度会越来越慢!


TA的精华主题

TA的得分主题

发表于 2015-3-17 09:11 | 显示全部楼层
本帖最后由 香川群子 于 2015-3-17 09:19 编辑
下标越界 发表于 2015-3-16 23:28
我的电脑上也是差不多到n=30就慢了,到n=40,已经达到6分钟。
使用循环代替递归,n=40,仅0.2秒不到。
下 ...

而一般循环计算代码,也可大大简化,无需使用数组。
  1. Function Fib(n%) '斐波那契数 循环算法
  2.     t = 0: t1 = 1
  3.     For i = 2 To n
  4.         t2 = t + t1
  5.         t = t1: t1 = t2
  6.     Next
  7.     Fib = t1
  8. End Function
复制代码
n>46时 计算结果>Long限制

…………
或者使用数组记录1-n全部计算结果时:
  1. Function Fib2(n%) '斐波那契数 返回数组结果
  2.     ReDim a(n)
  3.     a(1) = 1
  4.     For i = 2 To n
  5.         a(i) = a(i - 1) + a(i - 2)
  6.     Next
  7.     Fib2 = a
  8. End Function
复制代码
测试代码为:
Sub test()
    MsgBox Join(Fib2(50), vbCr)
End Sub

计算1-50并输出列表。



TA的精华主题

TA的得分主题

发表于 2015-3-17 14:31 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
香川群子 发表于 2015-3-17 08:48
你的代码可以大大简化:

首先,递归的代码:这是If 结构的横向写法。

n=30时,调用函数的次数是1664079次。n=1,2,3……30的次数总和是4356586次。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

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

GMT+8, 2024-3-29 00:14 , Processed in 0.047921 second(s), 7 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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