“递归”的开销，并不总是很大

今天跟群友讨论，发现很多朋友对递归存在一定偏见，其中有位朋友给出代码对比，证实递归性能比循环要差，递归的代码大概是这样：

int fib_recur1(int n)
{
	if (n == 1)
		return 1;
	if (n == 2)
		return 1;
	return fib_recur1(n - 1) + fib_recur1(n - 2);
}

“竞争对手”循环的代码大概是这样：

int fib_loop(int n)
{
	int n1, n2, i, tmp;
	n1 = 1;
	n2 = 1;
	for (i = 2; i < n; i++) {
		tmp = n2;
		n2 = n1 + n2;
		n1 = tmp;
	}
	return n2;
}

这种写法下，循环版肯定快了一个数量级。但这个并不是“递归”和“循环”的对比，而是两种不同计算方式的对比。

如果要使用相同的计算方式，递归代码应该是下面这样：

int fib_recur2_(int n1, int n2, int cnt, int target)
{
	if (cnt < target)
		return fib_recur2_(n2, n1 + n2, cnt + 1, target);
	else
		return n2;
}

为了对外提供一样的接口，另用一个函数包装一下：

int fib_recur2(int n)
{
	return fib_recur2_(1, 1, 2, n);
}

补上一个main函数：

int main()
{
	printf("fib_recur1(10): %d\n", fib_recur1(10));
	printf("fib_loop(10): %d\n", fib_loop(10));
	printf("fib_recur2(10): %d\n", fib_recur2(10));
	return 0;
}

跑跑看：

$ gcc a.c && ./a.exe
fib_recur1(10): 55
fib_loop(10): 55
fib_recur2(10): 55

感兴趣的朋友可以做个性能测试。

在没有尾调用优化的情况下， 第二个递归版本空间开销肯定更大（存在多重栈帧），但是时间开销上应该是和循环版本差不多的。

希望这个小例子能够消除一部分人对递归的偏见，毕竟很多地方，递归可能就是唯一解，这个技能是需要达到一定熟练度的。