函数的递归

一、递归

1.什么是递归

在C语言中，递归就是函数自己调用自己。

把一个大问题层层转换为一个与原问题相似，但规模较小的子问题来解决；知道子问题不能被拆分，递归就结束，所以递归的思想方式就是把大事化小的过程。

2.递归的限制条件

递归中存在限制条件，当满足这个限制条件的时候，递归便不再继续。

每次递归调用后越来越接近这个限制条件。

3.例题

请运用递归的思想完成数字n的阶乘（n为正整数）。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int fac(int n)
{
	if (n==1)
	{
		return 1;
	}
	else
	{
		return fac(n - 1) * n;
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	int c = fac(n);
	printf("%d", c);
	return 0;
}

 二、迭代

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

函数不返回时，函数对应的栈帧空间就一直被占用，所以如果函数调用中存在递归调用的话，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不在继续，开始回归，才会逐渐释放栈帧空间。

此时我们就可以运用迭代的方式来完成。

例题

计算第n个斐波那契数列的值。

1.用递归的方式来解决

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int fib(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		return fib(n - 1) + fib(n - 2);
	}
}
int main()
{
	int n;
	scanf("%d", &n);        //此时虽然能计算出结果但是当n的值比较大时计算的时间就比较长，具体原因上面有写。此时我们应该考虑用迭代的方式来写。
	int c = fib(n);
	printf("%d", c);
	return 0;
}

2.用迭代的方式解决

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int fib(int n)
{
	int a = 1, b = 1, c = 1;
	if (n<=2)
	{
		return 1;
	}
	while (n>=3)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n;
	scanf("%d", &n);
	int c = fib(n);
	printf("%d", c);
	return 0;
}