【通关函数的递归】--递归思想的形成与应用
目录
一.递归的概念与思想
1.定义
2.递归的思想
3.递归的限制条件
二.递归举例
1.求n的阶乘
2.顺序打印一个整数的每一位
三.递归与迭代
前言:上篇博文分享了扫雷游戏的实现，这篇文章将会继续分享函数的递归相关知识点，让大家了解并掌握递归的思路；
往期回顾:
【趣味小游戏】--扫雷游戏
一.递归的概念与思想
1.定义
---递归其实是一种解决问题的方法，在c语言中递归就是函数自己调用自己，举个最简单的例子:
#include <stdio.h>
int main()
{printf("hehe\n");main();//main函数中⼜调⽤了main函数return 0;
}上述就是一个简单的递归程序，只不过上面的递归只是为了演示递归的基本形式，不是为了解决问题，代码最后也会陷入死递归，导致栈溢出(stack overflow)。
2.递归的思想
把一个大型复杂问题层层转化为一个与原问题相似，但规模较小的子问题来求解；直到子问题不能再拆分，递归就结束了。所以递归的思考方式就是把大事化小的过程。
--递归中的递就是递推的意思，归就是回归的意思。
3.递归的限制条件
递归在书写的时候，有两个必要条件：
--递归存在限制条件，当满足这个限制条件的时候，递归便不再继续。
--每次递归调用之后越来越接近这个限制条件。
在下面的举例中，我们会逐步体会这两个条件。
二.递归举例
1.求n的阶乘
n的阶乘的递归公式：
所以我们就可以写出函数Fact求n的阶乘；
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>int Fact(int n)
{if (n == 0)return 1;elsereturn n * Fact(n - 1);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fact(n);printf("%d", ret);return 0;
}画图推演：
2.顺序打印一个整数的每一位
Print(n)如果n是1234，那表⽰为Print(1234) //打印1234的每⼀位其中1234中的4可以通过%10得到，那么Print(1234)就可以拆分为两步：1. Print(1234/10) //打印123的每⼀位2. printf(1234%10) //打印4完成上述2步，那就完成了1234每⼀位的打印那么Print(123)⼜可以拆分为Print(123/10) + printf(123%10)所以我们就可以据此写出代码:
void Print(int n)
{if (n > 9){Print(n / 10);}printf("%d ", n % 10);
}
int main()
{int m = 0;scanf("%d", &m);Print(m);return 0;
}画图推演：
三.递归与迭代
我们直接通过求第n个斐波拉契数来直观的了解一下两种方法；
1.递归
先看下递归的公式
#include<stdio.h>int fib(int n)
{if (n <= 2)return 1;elsereturn fib(n - 1) + fib(n - 2);
}
int main()
{int n = 0;scanf("%d", &n);int ret = fib(n);printf("%d\n", ret);return 0;
}
2.迭代(可以简单理解为循环)
#include<stdio.h>int fib(int n)
{int a = 1;int b = 1;int c = 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\n", ret);return 0;
}--通过这两个方法可以看出递归虽好，但是也会引入一些问题，所以一定不要迷恋递归。比如这里数大了之后计算就非常沉余了。迭代的方法去实现这个代码，效率就要高出很多了。
结语:感谢大家的支持，如果有兴趣的话，大家可以用递归的方法来尝试解决一下青蛙跳台问题和汉诺塔问题；