1. 什么是递归
2. 递归的举例
3. 递归与迭代

1. 什么是递归

递归就是一种解决方法，在C语言中，递归就是函数调用自己。

下面是一个简单的递归C语言程序：

  #include <stdio .h>

  int main()
  {
      printf("hello world\n");
      main();//main函数中又调用了main函数
      return 0;
  }

如上注释，main会递归调用自己，这样只是为了展示递归的基础程序，不是为了解决问题，所以程序会进入死循环，导致栈溢出。

1.1.递归的思路
   我们可以把它当做跟for，while等循环解决问题一样，当成一种解决问题的方法，但它主要是把大问题化解成小问题，主要思路主要是递推跟回归，接下来我带你们慢慢体会

1.2.递归的限制条件
跟for，while一样，它也有限制条件，不过它只有两个限制条件。
·递归需要有个限制条件，这个限制条件将关乎递归的结束
·每次递归过后都越来越接近限制条件

1.3.函数递归的优缺点

优点：函数递归只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
缺点：①如果函数递归使用不恰当，会导致栈溢出，②函数不返回，函数对应的栈帧空间就一直占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。这样就会大大占用栈帧空间，同时大大降低代码的执行效率。

关于函数栈帧如下：

在C语言中每一次函数调用，都需要为本次函数调用在内存的栈区，申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。

2. 递归的举例与实现

我们了解了递归的底层逻辑，接下来我们来看几个程序来看一下递归如何实现

2.1求n的阶乘
题目∶计算n的阶乘（不考虑溢出）。
2.1.1分析跟代码实现

n 的阶乘的公式:n!=n*(n-1)!

从中我们发现，这个思路就是把一个数的阶乘换成比它小一个的数的阶乘，然后一层一层把大问题细小化，其中的限制条件就是n＞＝0。

上面的函数Fact函数就是递归调用的函数，其中的特殊情况就是当n＝0时，Fact＝1，那我们就可以写出这个函数，假设Fact(n)就是求n的阶乘，那么Fact(n-1)就是求n-1的阶乘，函数

如下∶

  int Fact(int n)
  {
      if(n==0)
          return 1;
      else
          return n*Fact(n-1);
  }

！！！运行结果不需要考虑n太大的问题，n太大存在溢出。

如果还是觉得难懂的话，下面有个图可以直观体现出递归思路

而如果我们不用递归的话就只用循环的话，一层循环就可以了，代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
	int i = 0;
	int n = 0, end = 1;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		end *= i;
	}
	printf("%d", end);
	return 0;
}

 2.2顺序打印输入一个整数的每一位

例如∶输入1234  打印1 2 3 4

2.2.1分析和代码实现

解题思路∶当输入n的值是一位数，输出的n，反之则拆分n的每一位。而我们就需要取模跟取余的方式得到n的每一位
例如1234%10＝4，1234%10＝123（整型会自动约分为整数）然后一步一步得到每一位。
但这种情况如果直接输出的话就会输出4 3 2 1，所以我们可以用递归的方式反向输出，这样就可以输出1 2 3 4了

可以用下面的表达式来体现递归的方法

Print(1234)
==>Print(123)                 + printf(4)
==>Print(12)           + printf(3)
==>Print(1)   + printf(2)
==>printf(1)

Print函数的限制条件是当数字为一位数时，返回所有值，然后递归结束。下面是代码实现∶

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int Print(int x)
{
	if (x > 9)
	{
		Print(x / 10);
	}
	printf("%d ", x % 10);

}
int main()
{
	int n = 0;
	scanf("%d", &n);
	Print(n);
	return 0;
}

 2.3模拟实现strlen函数
例如∶输入abc   输出3

2.3.1分析和代码实现

首先我们要知道strlen函数是计算字符串‘\0’之前的长度，但我们如果要实现的话就需要设计一个my_strlen函数，这个函数每遇见一个衣服，函数值加1，直至到‘\0’结束

可以用下面的表达式来体现递归的方法
my_strlen(abc)--------------这里是指针在移动1+my_strlen(bc)
1+my_strlen(b)
1+my_strlen(‘\0’)
当满足我们的限制条件’\0’时，返回0，然后回归

my_strlen函数限制条件就是‘\0’，下面是代码实现

int my_strlen(char* str)
{

	if (*str != '\0')
	{
		return 1 + my_strlen(str + 1);//strlen函数的模拟实现方式
	}
	return 0;
}
int main()
{
	char arr[] = "abc";
	int ret = my_strlen(arr);
	printf("%d", ret);
	return 0;
}

2.4求n的k次幂
例如∶输入3 3 输出27
2.4.1分析和代码实现

解题思路∶首先对k进行分析，当k＝0时，无论n为几，函数最后返回值都为1，当k＞1时，每一次递推就乘以n，而k-1，直至k＝0。
！！！其中有一个隐含条件，就是k不会＜0。
同样也可以用下面的表达式来体现递归
n＝3  k＝3
Pow（3，3）
n*Pow（3，3-1）
n*Pow（3，2-1）
n*（3，1-1）
当k＝0时，函数返回1
 

下面是代码实现

int Pow(int x, int y)
{
	while (y)
	{
		return x*Pow(x, y - 1);
	}
}
int main()
{
	int n = 0, k = 0;
	scanf("%d %d", &n, &k);
	int c=Pow(n, k);
	printf("%d", c);
	return 0;
}

3.递归与迭代

我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰，但是这些问题的迭代实现往往⽐递归实现效率更⾼。
当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。二者是相辅相依的。
下面我们用一个题来看下他们之间的区别

3.1斐波那契数列（递归实现与迭代实现）
3.1.1递归分析和代码实现
解题思路∶斐波那契系数是前两项加起来等于后一项：1，1，2，3，5，8，13…,所以我们可以以n＜=2为限制条件，当n=1或2时，返回1，然后到n=3项时就是n=1项和n=2项之和，然后依次往后推，即Fib(n)就是Fib(n-1)和Fib(n-2)之和。
可以用下面的表达式来体现递归
Fib(n)，Fib(n-1) + Fib(n-2)，Fib(n-2)+Fib(n-3) , Fib(n-3)+Fib(n-4)…一直递推下去，直至到Fib(1)和Fib(2)返回值为1，然后回归，得到第n个斐波那契数。
下面还有一个图来帮助我们设计Fib函数

递归代码实现∶

int Fib(int x)
{
	if (x <= 2)
	{
		return 1;
	}
	else
	{
		return Fib(x - 1) + Fib(x - 2);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", n);
	return 0;
}

3.1.2迭代分析和代码实现
解题思路∶可以参考上面递归实现的思路，我们可以用三个变量相互替换来解决，n1为第一项，n2为第二项，tmp为第三项，运用while()循环，每一次循环n就减1，直到n=2，最后输出tmp。
！！！限制条件当n＜＝2，输出的值都是1，反之当n＞2时，循环开始，n＜＝2时，循环结束
下面是迭代代码实现

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	if (n <= 2)
	{
		return 1;
	}
	while(n>2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", ret);
	return 0;
}

3.2斐波那契数列中递归与迭代的区别
当我们尝试输入50时，我们可以发现递归的计算时间会非常长，这个计算所花费的时间说明递归的效率是非常低的，这是为什么呢？
下面一张图可以带给我们答案

其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计算，⽽且递归层次越深，冗余计算就会越多。而这些程序的计算结果不会共享，每次计算都会重新计算，这是因为函数栈帧的创建与销毁，每次调用函数都会在函数栈帧上开辟空间，同时完成函数是有要销毁这些空间。这样就大大降低了运行效率。

而当我们用迭代的方法时，会发现其实现的效率就比递归的效率高多了，这是为什么呢？
这是因为每一次循环，n1,n2,tmp会被赋值，代码执行次数大大减少，也就大大提高了代码的执行效率。