这是一个关于函数递归的相关问题

图片说明

这个例子中,rentun 里出现的递归函数,这是传说中的尾递归吗?
感觉这种递归不会占太多内存。因为执行return 就开始释放内存了。
return +递归函数,这种的

应该是1级函数释放掉,执行2级return 的函数,然后2级return 的函数,释放掉,执行3级的,其实用的差不多都是相同位置的内存,我的理解没错吧

1个回答

不是尾递归,因为f被递归调用2次,无论先算前一个表达式或者后一个表达式,都需要一个变量来缓存。因此不能不需要堆栈。

long f1(int m, int i, int a, int b);

long f(int m)
{
if (m < 3) return 1;
return f1(m, 3, 1, 1);
}

long f1(int m, int i, int a, int b)
{
if (i > m) return b;
b = a + b;
a = b - a;
return f1(m, i + 1,  a, b);
}

这是尾递归(我是指f1函数,作为最初的f不是递归),等价的循环:

long f(int m)
{
int a = 1;
int b = 1;
for (int i = 3; i <= m; i++)
{
b = a + b;
a = b - a;
}
return b;
}

但是要注意,c语言并不能把尾递归转换成循环,只是在逻辑上有这种等价关系。因此即便按照我给的代码,仍然还是需要堆栈存储,还是有递归深度的限制。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐