递归入门:使用递归的方法求n! #

[题目描述] #

求n!,其中0<=n<=10,其中0!=1.

[题目分析] #

我们设,那么如果我们想求:,明显我们只要知道的值就可以求出的值,因为.由此我们可以想到下面的思想:

这个大问题可以通过问题规模小一点的问题:得到答案，同样也可以通过这种方式分解成更小的问题，然后依次分解直到分解到最简单的问题.这个就是边界，正因为有边界的存在，我们的问题才不会一直的分解下去。

这个大问题和较小的问题相似，只是规模更小.这正是此问题可以使用递归方法的核心。

我们得出下面的公式:

使用递归解决问题 #

当然我们可以使用前面学习的递推法来解决这个问题,但是这里我们主要的目的是来学习递归.

#include <cstdio>

int factorial(int x){
    if(x == 0) //边界条件
        return 1;
    return x*factorial(x-1);
}

int main(){
    int n;
    scanf("%d",&n);//输入数字
    int ans = factorial(n);
    printf("the answer of %d! is:%d",n,ans);
    return 0;
}

递归函数factorial的理解 #

请先看动画演示：递归的原理:factorial

还记得我们前面讲过的函数调用的原理吗,其时我们只要按这个方法来理解.

函数分为两个部分:局部变量部分,代码部分

在调用函数的过程中,局部变量存在调用栈中,然后执行代码部分来改变局部变量的值,最后返回结果,跳转到调用函数处的下一行.

一个函数之所以能自己调用自己,是因为它在调用自己的时候,会在调用栈上产生一个新的局部变量区域,然后去执行代码部分,修改这个新的局部变量区域,相当于有了两个函数.

针对这个问题递归是有边界，边界就是x==0

• 当我们不停的分解问题（方块向上磊积的时候）叫做递归的前进
• 当我们解决问题（拿下方块）叫做递归的回溯

递归的机器实现 #

这里请看视频里的讲解

关于函数的信息都存放在栈中

gdb -tui filelayout asmbacktracebacktrace Ninfo argsinfo registersinfo frameframe Nx /40xw 显示内存里的内容 esp,rsp 栈顶的地址 ebp,rbp 栈帧的信息

什么情况下用递归 #

如果一个问题可以分解，且分解出来的子问题和原问题相似（可以用一方式解决，也说明这个子问题同样也可以分解） 而且子问题的规模变小了，那这样的题目就可以用递归。后面深度优先搜索章节还会详细的学习递归。