循环转换为尾递归

xitijie 2012-08-25 11:24:38

斐波那契问题:

　　　　　　非递归解决方法:

void FaboLoop(int n)
{
int a=0;
int b=1;
int c;
int i;

if(n==0)
{
c=1;
}
else
{

if(n==1) c=1;
else
{

for(i=2;i<=n;i++)
{
c=a+b;
a=b;
b=c;
}
}

}

printf("%d\n",c);
}

　　　　尾递归方法:

int FaboTailRec(int n, int a, int b)
{

if (n==0)
{
return a;
}

return FaboTailRec(n-1, b, a+b);

}

问题:我想找到根据非递归循环来转换成尾递归的一种方法,而上面非递归循环的方法中就用了三个参数,所以我想写一个尾递归是采用a,b,c三个参数的即FaboTailRec(n, a, b,c),但是遇到了问题,

非递归中
c=a+b;先执行这一句,于是FaboTailRec(n-1, , ,a+b);第

三个参数确定

　　 a=b; 再执行这句,是给a赋值,但是形参是从右到左入

栈的,也就是说第二个修改的值应该是b,但是这里

要修改的是a,问题就在这里

　　

所以,请告诉我怎么解决这个问题,或者跟我说说循环怎么转换为尾递归的技巧

...全文

252 5 打赏收藏转发到动态举报

写回复

用AI写文章

5 条回复

切换为时间正序

请发表友善的回复…

发表回复

mmqmjy 2012-08-26

打赏
举报



unsigned fabo_do(unsigned n, unsigned a, unsigned b)

{

	if (n == 0) {

		return b;

	} else {

		return fabo_do(n - 1, b, a + b);

	}

}



unsigned fabo(unsigned n)

{

	if (n <= 2) {

		return 1;

	} else {

		return fabo_do(n - 2, 1, 1);

	}

}

mmqmjy 2012-08-26

打赏
举报

你这样已经是尾递归了

xitijie 2012-08-26

打赏
举报

[Quote=引用 4 楼的回复:]

C/C++ code

unsigned fabo_do(unsigned n, unsigned a, unsigned b)
{
if (n == 0) {
return b;
} else {
return fabo_do(n - 1, b, a + b);
}
}

unsigned fabo(unsigned n)
{
……
[/Quote]

瞎写!

xitijie 2012-08-25