(23)王道数据结构-栈在递归中应用

函数调用

函数调用的特点：最后被调用的函数最先执行结束(LIFO)
函数调用时，需要用一个栈存储调用返回数据，实参，局部变量

递归案例

适合用递归算法解决的，可以把原始问题转换为属性相同，但问题规模较小的问题。
例如：阶乘、斐波那契数列

#include<stdio.h>
int factorial(int n);
int main(void) {
    int x = factorial(10);
    printf("10的阶乘为%d\n", x);
    return 0;
}
//计算正整数n!
int factorial(int n) {
    if (n==0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

递归调用时，函数调用栈可称为“递归工作栈”没进入一层递归，就将递归调用所需信息压入栈顶。每退出一层递归，就从栈顶弹出相应信息
缺点：太多层递归可能会导致栈溢出