函数递归知识-平芜编程栈

函数递归知识

文章目录

函数递归知识
一.什么是递归
- （一）递归的思想
- （二）递归的限制条件
二.递归举例
- （一）举例1：求n的阶乘
- - 1.分析和代码实现
  - 2.画图推演
- （二）举例2：顺序打印一个整数的每一位
- - 1.分析和代码实现
  - 2.画图推演
三.递归与迭代
- （一）递归的缺陷
- （二）举例：求第n个斐波那契数
- - 1.递归方式
  - 2.迭代方式

一.什么是递归

递归其实是一种解决问题的方法，在C语言中，递归就是函数自己调用自己。
最简单的C语言递归代码：

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

上面的递归只是为了演示递归的基本形式，代码最终也会陷入死递归，导致栈溢出（Stack overflow）。

（一）递归的思想

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

（二）递归的限制条件

递归在书写的时候，有2个必要条件：

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

二.递归举例

（一）举例1：求n的阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1，自然数n的阶乘写作 n!。
题目：计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字累积相乘。

1.分析和代码实现

n的阶乘的公式： n！ = n * (n − 1)!
n的阶乘和n-1的阶乘是相似的问题，但是规模要少了n。有一种有特殊情况是：当 n==0 的时候，n的阶乘是1，而其余n的阶乘都是可以通过上面的公式计算。
写出 n 的阶乘的递归公式如下：

假设Fact(n)就是求n的阶乘，那么Fact(n-1)就是求n-1的阶乘，函数如下：

intFact(intn){if(n==0){return1;}else{returnn*Fact(n-1);}}

运行测试：（不考虑n太大的情况，n太大存在溢出）：

2.画图推演

该递归限制条件是n==0，每次递推n-1越来越接近这个限制条件，当满足这个限制条件的时候，递推便不再继续，开始回归。

（二）举例2：顺序打印一个整数的每一位

输入一个整数m，按照顺序打印整数的每一位。
比如：
输入：1234 输出：1 2 3 4

1.分析和代码实现

关于这个题目，首先想到的是，怎么得到这个数的每一位。
如果n是一位数，就是n自己，n超过1位数，就得拆分每一位。

1234%10就能得到4，然后1234/10得到123，这就相当于去掉了4 然后继续对123%10，就得到了3，再除10去掉3，以此类推，不断的 %10 和 /10 操作，直到1234的每一位都得到。但是有个问题就是得到的数字顺序是倒着的。

假设想写一个函数Print来打印n的每一位：

Print(1234)//打印1234的每⼀位

其中1234中的4可以通过%10得到，那么Print(1234)就可以拆分为两步：

Print(1234/10)//打印123的每一位
printf("%d ",1234%10)//打印4

Print(1234)打印1234每一位，拆解为先Print(123)打印123的每一位，再打印得到的4。
Print(123)打印123每一位，拆解为先Print(12)打印12的每一位，再打印得到的3。
直到Print打印的是一位数，直接打印就行。
函数如下：

voidPrint(size_tn)//打印n的每一位{if(n>9){Print(n/10);}printf("%zu ",n%10);}

运行测试：

2.画图推演

该递归限制条件是n为个位数（n<=9)，每次递推n/10越来越接近这个限制条件，当满足这个限制条件的时候，递推便不再继续，开始回归,逐个打印。

三.递归与迭代

（一）递归的缺陷

递归是一种很好的编程技巧，但是可能被误用，就像举例1一样，看到推导的公式，很容易就被写成递归的形式：

intFact(intn){if(n==0){return1;}else{returnn*Fact(n-1);}}

Fact函数可以产生正确的结果，但是在递归函数调用的过程中涉及一些运行时的开销。

在C语言中，每一次函数调用，都需要在内存的栈区申请一块内存空间，用于保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。
函数不返回，函数对应的栈帧空间就一直占用，所以如果函数调用中存在递归调用，每一次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。

如果采用函数递归的方式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出（stack overflow）的问题。
如果不想使用递归，通常就是迭代（循环）的方式。
例如：计算 n 的阶乘，可以产生1~n的数字累计乘在⼀起的。

许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更加清晰，但是这些问题的迭代实现往往比递归实现效率更高。
当一个问题非常复杂，难以使用迭代的方式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

（二）举例：求第n个斐波那契数

1.递归方式

计算第n个斐波那契数，是不适合使用递归求解的，但是斐波那契
数的问题通过是使用递归的形式描述的，如下：

看到这公式，很容易诱导我们将代码写成递归的形式：

intFib(intn){if(n<=2){return1;}else{returnFib(n-1)+Fib(n-2);}}

运行测试：

当n输入为50的时候，需要很长时间才能算出结果，这也说明递归的写法是非常低效的。
原因：递归程序会不断的展开，在展开的过程中，在递归的过程中会有重复计算，而且递归层次越深，冗余计算就会越多。

代码测试：

在计算第30个斐波那契数的时候，使用递归方式，光是第3个斐波那契数就被重复计算了317811次，这些计算是非常冗余的。

2.迭代方式

斐波那契数的前2个数都为1，然后前2个数相加就是第3个数，从前往后，从小到大计算就行了。

#include<stdio.h>intFib(intn){inta=1,b=1,c=1;while(n>2)//不知循环次数用while循环，n<=2时不用计算，直接返回1，所以c初始化1{c=a+b;a=b;b=c;n--;}returnc;}

函数递归知识