【算法】递归：递归优化之尾递归

引言：在以往我发过一篇过于通过分析法去理解递归求解递归的博客文章，那篇文章主要介绍了如何去求解递归问题。而在这篇文章中，我会介绍一下如何去优化递归，顺带还会去分析一下递归算法的性能，这篇文章的目的是一个小小的分享，希望大家能在此有收获。

摘要：文章首先会先通过斐波那契数列来复习在以往介绍的解决递归的方法，然后在通过这个例子去分析递归法的不足之处，最后将会介绍一下关于递归的优化策略，并举例实现。

一. 递归法求斐波那契数列

int Fibonacci_sequence(int n) {
    // 终止条件
	if (n == 1 || n == 2)
		return 1;
	else
        // 分解 解决子问题 合并子问题
		return Fibonacci_sequence(n - 1) + Fibonacci_sequence(n - 2);
}

二. 递归法的不足

在上述篇幅我们解决了斐波那契额的问题，可以当我们把 n 输入到 50 时，我们就会发现，我们的程序仿佛已经死掉了，其实这主要的原因是在于在递的过程中，因为上一步计算需要先完成下一步计算才可以，所以每个函数在函数栈帧中会占用相应的内存，并且不被释放，知道回归合并为止。比如在此处，输入 n = 50 后，会有大量的内存遗留，甚至导致栈溢出，出现假死。不仅如此，还会出现像重复计算，在函数栈帧的创建与销毁需要时间与空间等问题。

总体来说，主要问题有：

递归使用函数栈帧模拟循环的过程，栈帧的开辟和销毁都需要时间；
在递归使用函数栈帧的过程中，如果可能无法及时的释放内存而导致占用内容空间，甚至还会导致栈溢出；
可能会出现大量的重复计算，提高时间复杂度

三. 递归优化——尾递归

所谓的尾递归，我们先给出概念，就是当编译器检测到尾递归时，覆盖当前栈帧，而不是去建立一个新的栈帧，这样只需要占用一个函数栈帧空间，防止了内存的大量浪费。

为了解尾递归，我们需要用尾调用入手，掌握其基本原理，再运用于尾调用。

void test_1() {
	printf("test====>1\n");
}
void test_2() {
	printf("test====>2\n");
	return test_1();
}
void test_3() {
	printf("test====>3\n");
	return test_2();
}

int test_4() {
	return 1;
}
int test_5() {
	int ret = test_4();
	return ret;
}

int test_6() {
	return test_4() + 1;
}

void test_7(){
	test_7();
}

void f(){
	.........
	
	return g();
}

int Fibonacci_sequence_better(int n,int temp1,int temp2) {
	if (n == 1 || n == 2)
		return temp2;
	else
		return Fibonacci_sequence_better(n - 1, temp2, temp1+temp2);	
}

int factorial(int n, int temp) {
	if (n == 1)
		return temp;
	else
		return factorial(n - 1, temp * n);
}

四. 总结尾递归书写方法

尾递归从本质上来说就是覆盖原有的栈帧空间，防止内存过度占用，而实现的主要条件就是要求函数其中调用位置与内部变量不需要再被用到，为此我们所想出的解决办法就是将这些数据作为中间变量出现，如此就可以防止原函数无法出栈的情况。最后既然是递归，仍旧需要调用自身，完成递归的过程。

为此作者通过上述例题进行进行一个简单的提炼，希望能帮助大家，同时尾递归的运用离不开理解与联系，所以大家必须要着手于实践之中。提炼内容如下：

//n：迭代次数
//temp1与temp2：将需要使用的局部变量通过参数的形式出现
int Fibonacci_sequence_better(int n,int temp1,int temp2) {
	//终止条件
	if (n == 1 || n == 2)
		// temp2 表示累计递归结果
		return temp2;
	else
		//递归调用自身
		return Fibonacci_sequence_better(n - 1, temp2, temp1+temp2);	
}

五. 总结

在介绍递归的文章中，作者写了两篇，其中介绍了自己如何去解决递归问题，然后在本篇中完成了对递归优化的拓展。博主认为本篇所讨论的只是扩展内容，不需过度深究，了解即可，更重要的是解决递归问题的方法。

最后对两篇文章进行概括：

分析解决递归问题：分解问题、解决子问题、合并子问题得到原问题答案、终止条件；
尾递归优化：将局部变量转换为中间参数，在最后调用自身；

递归问题的理解以及运用是需要练习的，所以在掌握理论知识后，仅需要进行大量练习，这样可以巩固所学，同时还可以有自己更新的理解。

补充：

代码将会放到： https://gitee.com/liu-hongtao-1/c–c–review.git ，欢迎查看！
欢迎各位点赞、评论、收藏与关注，大家的支持是我更新的动力，我会继续不断地分享更多的知识！
所以在掌握理论知识后，仅需要进行大量练习，这样可以巩固所学，同时还可以有自己更新的理解。