香川组合的递归代码

香川群子

AVEL 发表于 2012-7-10 21:20
递归一直都学不会。。 群子老师怎么学的？介绍经验。。

嗯。递归其实很简单。

要求：

0.  【申明公共变量】
   以便某些【数据】、【变量】在【主过程】和【递归过程】中都能够通用使用。
如： Public sj, jg(), m%, n%, r&
其中，sj 为数据数组，jg为结果数组，m,n为大小参数，r为结果数组的计数

一、 【主过程】 分三部分：
1.  读入原始数据(必要时做一些简单整理)，给公共变量赋值或初始化。
2.  调用递归过程
3.  输出递归计算结果

【注意】公共变量在每次代码运行结束后，也会继续留在内存中，
所以每次代码运行前，理论上对所有公共变量都要重新赋值或初始化。
一般变量都会赋值，所以问题不大，但千万不要忘记对计数值r也进行初始化归零，否则会产生计数错误。
        
二、【递归过程】至少有2部分
1. 结束递归的条件
2. 在循环或判断语句中，可以继续调用自身的代码过程（即进入下一阶层递归的过程）

例如：
Sub mndg(s$, i, t%) '递归过程代码，注意必须要有【参数】输入！

    If t = n Then '如果已经计算到最后第n列，则可结束递归了。
         【省略结果处理代码】
         r = r + 1 '计数值+1
         Exit Sub  '结束本次递归，返回到上一次递归进程。
    End If
    '以上，即为终止、结束递归的【条件】的代码。
   
    For j = i + 1 To m '循环过程等
        If sj(j, t + 1) <> "" Then Call mndg(s & ";" & j, 0, t + 1)  '符合条件时进入下一个递归过程。
    Next j


【注意事项】：
递归过程中，必须要有参数的输入如s,i.t，并通过递归计算过程改变参数结果，
并把新的结果作为参数输入到下一阶层的递归过程中去，
这个就是递归过程的输入和输出，

End Sub


………………
因此，
【递归过程】的必须条件，也可以说成是：
1. 参数输入  
   → 即获取 s,i,t参数

2. 本次递归计算 或 通过循环获取新的参数
   → 即循环获取新的参数： For j = i + 1 To m
        以及，s=s & ";" & j     （递归中间结果s的更新，加入符合条件的递归结果j）
                 i=0                 （下一次递归仍从0位置开始）
                 t=t+1             （本列处理完毕，递增进入下一列）

3. 新的参数输出到下一阶层的递归（调用递归）
    Call mndg(s & ";" & j, 0, t + 1)

4. 结束递归的条件（根据条件判断结束本次递归，返回到上一层递归进程。）
     If t = n Then
     ……结果处理
     Exit Sub
     End If

但是实际上，习惯上第4项的递归退出条件会写在代码开始，以确保每次新的递归过程不发生错误。

香川群子

AVEL，给你出个简单的题目：

写一个简单的递归过程，计算返回自然数1-N的总和 （即，1+2+3+……+N 求和）

香川群子

题目2：

写一个简单的递归过程，计算自然数N的阶乘。

即，1*2*3*……*N 求总乘积。

N就取100以内好了。

bluexuemei

1. Function s(n%)
   
2. If n = 1 Then
   
3.     s = 1
   
4. Else
   
5.     s = n + s(n - 1)
   
6. End If
   
7. End Function

复制代码

1. Function c(n%)
   
2. If n = 1 Then
   
3.     c= 1
   
4. Else
   
5.     c= n * c(n - 1)
   
6. End If
   
7. End Function

复制代码

香川群子

bluexuemei 发表于 2012-7-11 11:54

这个是给AVEL 出的题目啊。不是给你的。


另外，你的代码，是递归函数，不是递归过程的写法。

如果要改写成递归过程，你的代码该如何改？


…………
我写出的递归过程代码，经过测试，
速度比你快，堆栈占用比你少……

你的递归函数，只能计算到最大n=4376
而我的递归过程，可以计算最大n=4805
（不同的电脑硬件，可允许的堆栈占用不同，仅作参考。）


同样按照4370来计算时，我的速度比你快30%

呵呵。

bluexuemei

1. Option Explicit
   
2. Dim k As Double
   
3. Sub 递归()
   
4.     k = 1
   
5.     s2 100
   
6.     MsgBox k
   
7.   End Sub
   
8.    Sub s2(n As Integer)
   
9.     If n > 0 Then
   
10.       k = k * n
    
11.       s2 n - 1
    
12.      End If
    
13.    End Sub
    

复制代码

香川群子

阶乘代码的差别不大，最大计算值都是=170
工作表函数能计算的最大值也是=Fact(170)=7.25741561530799E+306

                                          72574156153079989673
96728211129263114716991681296451376543577
79890056184340170615785235074924261745951
14909912378385207766660225654427530253289
00773207510902400430280058295603966612599
65825710439855829425756896631343961226257
10949468067112055688804571933402126614528
00000000000000000000000000000000000000000


速度相差也不大，我的递归过程只比递归函数快了10%不到。

呵呵。

香川群子

回复Zamyi

递归方法不是一定需要公共变量，但很多时候应该使用公共变量以简化代码。


否则你可能需要每次都把相同的变量或数据，作为参数引入递归过程。

xwdys

请问，香川侠圣， 普通浏览 复制代码 下的嵌入代码框是如何做的？左边有序号。。。

香川群子

过程和函数，还是有很大区别的。

即，过程可以操作单元格，而函数只能获取计算结果。

下面出个题目，寻找同类 或者 简易迷宫。


在一个矩形单元格区域中，随机分布着 1 和 0
要求从区域中任意一个选中单元格开始，
如果上下左右是相同的值（0或1）则填上红色，
直至所有符合条件的相邻单元格被填满。



如附件：