C语言学好递归看这一篇就够了

前言

在一定的时间、空间限制下，人的体力有限，思维力也有限，递归思维对实践最有用的指导，就是把脑力集中于定义问题这个关键点上，不用去找解题的过程。定义（问题）即解决（问题），定义即解决！让大问题变成规模更小的问题并立即获得解决，以此作为基础，让我们轻松解决函数本身定义的问题。所以，递归在编程中同样是很重要的一个知识点。

提示：以下是本篇文章正文内容

一、递归是什么？

先来看一下定义：

程序调用自身的编程技巧称为递归（ recursion）。

简单来说，就是在一个函数里面调用函数自己本身。

举个例子：
用递归实现求第n个斐波那契数。

int Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

int main()
{
	//斐波那契数 1 1 2 3 5 8 13 21 34 51....,除前两位外，后一个数的值等于前两位相加
	int n = 0;
	printf("请输入你要查找的斐波那契数：");
	scanf("%d", &n);
	int ret=Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

C语言学好递归看这一篇就够了

所以，我们可以看到，所谓递归，其实就是一个函数里面调用函数自己本身。具体怎样调用的，我们下面再讲。

二、递归的两个必要条件

1、存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。

分析之后，我们可以得出两个点

1、结束条件
2、逼近条件

我们在使用递归的时候，需要满足这两个条件。

总结起来四个字――大事化小

继续举斐波那契数的例子：

C语言学好递归看这一篇就够了

三、递归是怎样运行的

我们通过一道题目来讲解。

题目：递归实现n的k次方
内容：编写一个函数实现n的k次方，使用递归实现。

【解决思路】
运用递归思路，我们只要找到递归结束条件和逼近条件。通过分析，我们可以画出下面这幅图。

C语言学好递归看这一篇就够了

【代码实现】

#include <stdio.h>
double power(int n,int k)
{
	if (k< 0)
	{
		k = -k;
		return 1 / (n*power(n, k - 1));
	}
	else if (k == 0)
		return 1;
	else if (k>0)
	{
		return n * power(n, k - 1);
	}
}
int main()
{
	int n = 0;
	int k = 0;
	printf("请输入一个整数：");
	scanf("%d", &n);
	printf("请输入要求的次方数：");
	scanf("%d", &k);
	double ret=power(n,k);
	printf("%1f\n", ret);
	return 0;
}

【画图详解递归思路】

C语言学好递归看这一篇就够了

通过图解，发现思路，我们** 存在限制条件k，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。**之后输出的时候就反过来回去。

这个就是递归的思路。

四、迭代与递归

不知大家有没有认真思考过上面的求斐波那契数的代码，它有什么问题？

C语言学好递归看这一篇就够了

如果我们这里求的是第50个斐波那契数呢？大家可以运行一下代码。可以发现，电脑运行了好久好久才算出结果，费时间。
如果求第10000个斐波那契数呢？程序就会崩溃。

为什么呢？
我们发现上面求斐波那契数的 Fib 函数在调用的过程中很多计算其实在一直重复。
因为我们在调用这个函数的时候，除前两位外，后一个数的值等于前两位相加。这就导致了我们不断重复计算

如图：

C语言学好递归看这一篇就够了

我们可以看到，由于前两个数相加等于后一个数，前两个数相加等于后一个数，所以我们会不断产生重复的计算。就会造成计算量非常大，效率极低。

那我们如何改进呢？
我们程序存东西的时候，存放在栈区。
如图：

C语言学好递归看这一篇就够了

在调试例子中的Fib函数的时候，如果你的参数比较大，那就会报错： `stack overflow（栈溢出）这样的信息。
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

那如何解决上述的问题：

将递归改写成非递归。使用static对象替代non-static局部对象。在递归函数设计中，可以使用static对象替代nonstatic局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销，
而且static对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。

这里我们介绍迭代。

什么是迭代呢？
【概念】

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

借用网上的图片来说明（侵删）

C语言学好递归看这一篇就够了

目前对于c语言来说，迭代可以简单认为是循环结构。

那么我们如何用迭代的方式求斐波那契数呢？
【代码如下】

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n>2)
	{
		c = a + b;//求出c的值
		a = b;//a赋值给b,也就是a作为b的值
		b = c;//b赋值给c，也就是b作为c的值
		n--;
	}
	return c;
}

int main()
{
	// 1 1 2 3 5 8 13 21 34 55,除前两位外，后一个数的值等于前两位相加
	int n = 0;
	printf("请输入你要查找的斐波那契数：");
	scanf("%d", &n);
	int ret = Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

C语言学好递归看这一篇就够了