C# 尾递归优化

何为尾递归

有时候我们使用递归来解决一些特定的问题,但是使用递归需要注意不要导致栈溢出,这是使用递归的一个常见问题,对于规模足够大的问题,使用递归必定会导致栈溢出。通常,我们可以通过尾递归进行优化,尾递归可以避免栈溢出的问题(暂且这样认为)。
尾递归并不是什么新奇的东西,理解起来很简单,对于递归,如果上层调用的返回结果不依赖子调用的结果,那么,这就是一个尾递归。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
///这是一个简单的尾递归例子
namespace tail
{
class Program
{
static void Main(string[] args)
{
var test=RetrieveData(100000000000000);
}

static long RetrieveData(long unit)
{
if (unit == 0)
return unit;
return RetrieveData(--unit);
}
}
}

等等,好像有什么地方不对

从上面的例子分析,代码依旧会导致栈溢出,不是吗?是的,聪明的你答对了。那为什么说尾递归可以避免栈溢出问题?当然,从刚才的结论看,这个问题提的并不准确,尾递归并不能避免栈溢出问题。
仔细想想,尾递归结构和循环结构是类似的,上面的尾递归可以写成:

阅读更多