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

Question

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

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

Answer 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语言并不能把尾递归转换成循环，只是在逻辑上有这种等价关系。因此即便按照我给的代码，仍然还是需要堆栈存储，还是有递归深度的限制。