函数递归的学习1

了解递归

递归是什么

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

递归的思想

把⼀个大型复杂问题层层转化为⼀个与原问题相似，但规模较小的子问题来求解；直到子问题不能再被拆分，递归就结束了。所以递归的思考方式就是把大事化小的过程。 递归中的递就是递推的意思，归就是回归的意思。

递归的注意要点

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

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

2.确保递归能到达所设条件，避免无限递归。

#include <stdio.h>
int main()
{
 printf("hehe\n");
 main();  //main函数中⼜调⽤了main函数 
 return 0;
}

如这段代码没有设置限制条件，就会死循环打印 ''hehe''，最终导致栈溢出。

学习的简单例子

1.求n的阶乘

1）. n的阶乘可以有循环简单求出。下面可以正确的求得 5 的阶乘为 120。

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

2）.也可以用使用递归的方法

#include <stdio.h>
int test(int n)
{
	if (n == 1)     //代码的限制条件
		return 1;
	else return n * test(n - 1);   //每一次递归，更接近n为1的这个条件
}
int main()
{
	int n = 5;
    scanf("%d",&n);
	int num = test(n);
	printf("%d", num);
	return 0;
}

在 test 函数中，当不满足 n 为 1 这个限制条件时，函数就会不断递推，每一次递推 n 就减一，当 n 为一时，函数就开始回归，最后将所得的结果，作为函数最后的返回值，函数调用完成。

顺序打印⼀个整数的每⼀位

输⼊⼀个整数m，按照顺序打印整数的每⼀位。比如：

输⼊：1234输出：1 2 3 4

输⼊：520 输出：5 2 0 

#include <stdio.h>
void test(int n)
{
	if (n > 10)   //限制条件
	{
		test(n / 10);   
	}
	printf("%d ", n%10);  
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	test(n);
	return 0;
}

对于一个数，对它模 10 就可以得到它的最低位；每得到一次它的最低位，都对它除以 10，就可以得到它每一位上的数字。通过递归，就可以实现这一段代码。

在递归中，函数自己调用自己，不满足限制条件时，一步步执行递推的过程；

满足限制条件后，再逐步回归，将每一次调用函数后的回归的步骤执行，使函数整体的运行完成。

典型例子 -- 求第n个斐波那契数

1.递归的实现

这是求解斐波那契函数的数学公式。即第一位和第二位为 1，之后的每一位都等于前两个数之和。

根据公式可以很容易的写出代码。

#include <stdio.h>
int Fib(int n)
{
	if (n <= 2)         //公式的
		return n;       //代入
	else return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d", ret);
	return 0;
}

但是当n较大时，这段代码的效率就没有那么高，在递归的不断展开中很多数不断重复出现，导致计算机运行大大降低，我们可以测试一下计算第 40 个斐波那契数时，2 出现的次数。

#include <stdio.h>
int count = 0;
int Fib(int n)
{
	if (n == 2)
		count++;
	if (n <= 2)
		return n;
	else return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	printf("%d\n", count);
	return 0;
}

单单是数字 2 出现的次数都有六千多万次，这无疑大大降低了运算效率。

以迭代的方式求解斐波那契数。

因此，为了提高效率，我们可以用迭代的方式求解斐波那契数。

#include <stdio.h>
int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 0;
	if (n < 3)
		return 1;
	else
	{
		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\n", ret);
	return 0;
}

在这个代码中，我们可以瞬间算出较大的斐波那契数，如上述的第 55 个斐波那契数，但以递归实现的函数要计算第 55 斐波那契数则需要较长的等待。

所以在实现代码时，应考虑其运行效率，合理选择实现代码的方式。

。。。