一列数的规则如下: 1、1、2、3、5、8、13、21、34…… 求第30位数是多少, 用递归算法实现。
答:public class MainClass
{
public static void Main()
{
Console.WriteLine(Foo(30));
}
public static int Foo(int i)
{
if (i <= 0)
return 0;
else if(i > 0 && i <= 2)
return 1;
else return Foo -1) + Foo(i – 2);
}
}
为了演示这尾递归执行的顺序 本人只执行 Foo(5), 执行i从5到2 等于2返回1 当返回1 下个步骤是执行的什么?是执行Foo(i – 2)这个函数吗?
答:public class MainClass
{
public static void Main()
{
Console.WriteLine(Foo(30));
}
public static int Foo(int i)
{
if (i <= 0)
return 0;
else if(i > 0 && i <= 2)
return 1;
else return Foo -1) + Foo(i – 2);
}
}
为了演示这尾递归执行的顺序 本人只执行 Foo(5), 执行i从5到2 等于2返回1 当返回1 下个步骤是执行的什么?是执行Foo(i – 2)这个函数吗?
解决方案
40
Foo(i)当I是1或2时,函数都返回1,此时,递推完成;以后就回归了,见下图,图有点丑
![研究了一天的尾递归 还是又一些不清楚 研究了一天的尾递归 还是又一些不清楚](https://www.codebye.com/wp-content/uploads/2016/07/-803600422984002337.jpg)
所谓回归,就是计算上图中的1+1+1+1+1,也是我们要的结果
![研究了一天的尾递归 还是又一些不清楚 研究了一天的尾递归 还是又一些不清楚](https://www.codebye.com/wp-content/uploads/2016/07/-803600422984002337.jpg)
所谓回归,就是计算上图中的1+1+1+1+1,也是我们要的结果