MyException - 我的异常网
当前位置:我的异常网» C# » 一个递归的算法.很简单的代码.但没法悟出其中的道理

一个递归的算法.很简单的代码.但没法悟出其中的道理.分数不多.希望有高人点明,在线~

www.MyException.Cn  网友分享于:2013-12-20  浏览:9次
一个递归的算法.很简单的代码.但无法悟出其中的道理.分数不多.希望有高人点明,在线~~
C#代码:

题:一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30位数是多少, 用递归算法实现。

答:
public class MainClass 

  { 

  public static void Main() 

  { 

  Console.WriteLine(Foo(10)); 

  } 

  public static int Foo(int i) 

  { 

  if (i <= 0) 

  return 0; 

  else if(i > 0 && i <= 2) 

  return 1; 

  else return Foo(i -1) + Foo(i - 2); 

  } 

  } 
我把程序DOWNLOAD下来调了一下..调的很郁闷.就这么简单的一块代码~淋漓尽致的把我给衬托出白痴的形像.
我把问题给揪出来:

当i=10的时候.它便跑到了
 return Foo(i -1) + Foo(i - 2);这一段 递归嘛.自减.我还懂一点点.这时候它又调自己了,还处于Foo(i -1)这块(应该还没运行到Foo(i - 2),我是这样理解.如果有误.请指明)
像这样如此类推的减下去.9,8,7,6,5,4,3,2 到2了. 好.问题出来了..到了二它返回一.调试的时候到返回一后它会跳出去"}" 之后呢.下一步它又跳到
  else return Foo(i -1) + Foo(i - 2);这是为什么呢~? 更让我奇怪的是.当跳到这一步的时候.我发现I的值竟然变成3了.这3是怎么算出来的?到底是为什么呢~? 我就是想不透~~我把代码改了一下else return Foo(i -1) + Foo(i - 2);改成else return Foo(i -1);但走的步骤还是一样~ 这是为啥哩?~ 哪位高人能让我恍然大悟.顺便能够附带一份简明的递归原理给我(不要太复杂.看不下去的..) 谢谢..本人分不够.只能拿出十分来以表谢意了..我现在是负资产.我还欠两张贴的分没还.望见谅~~

------解决方案--------------------
我也不是很懂,可能是这样
递归的原理应该是重新在内存中开一块出来执行函数,前面没执行完的就挂在那里,待会儿回来执行,所以那个i又变回成3了。
------解决方案--------------------
@代表当前运行点
1、求解Fab(5),@调用Fab(4)(跳到2),Fab(3),求和并返回//i=5,堆栈相对层次0
2、求解Fab(4),@调用Fab(3)(跳到3),Fab(2),求和并返回//i=4,堆栈相对层次1
3、求解Fab(3),@调用Fab(2)(跳到4),Fab(1)//i=3,堆栈相对层次2
4、求解Fab(2),@返回1,程序跳回返回点1//i=2,堆栈相对层次3
5、求解Fab(3),调用Fab(2)@(返回点1),Fab(1),求和并返回//i=3,堆栈相对层次2
6、求解Fab(3),调用Fab(2),@Fab(1)(跳到7)//i=3,堆栈相对层次2
7、求解Fab(1),@返回1,程序跳回返回点2//i=1,堆栈相对层次3
8、求解Fab(3),调用Fab(2),Fab(1)@(返回点2),求和并返回//i=3,堆栈相对层次2
9、求解Fab(3),调用Fab(2),Fab(1),求和并返回@(返回点3)//i=3,堆栈相对层次2
10、求解Fab(4),@调用Fab(3),(返回点3)Fab(2),求和并返回//i=4,堆栈相对层次1
。。。
好累。。。
------解决方案--------------------
这个数组的规律就是从第3位开始每个数都是前2个数之和。
return Foo(i -1) + Foo(i - 2); 这个就是把前两位加起来而已。
当i=3的时候Foo(3-1) = Foo (2) = 1 Foo(3-2) = Foo(1) = 1. 返回值就是1+1 = 2
当i=4的时候Foo(4-1) = Foo(3) = F00(2) + Foo(1) = 2 ,Foo(4-2) = Foo(2) = 1,返回值就是1+2 = 3
.....
当i=10的时候Foo(10-1) = Foo(9) = Foo(8) + Foo(7) = Foo(7) +Foo(6) + Foo(6) + Foo(5)=.....
递归就是按这个等式一步一步推导走下去直到Foo(1)或者Foo(2)的时候才停止。

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有