【C语言】函数的递归调用

阅读本文，需要对C语言的基础知识有所了解。C语言基础，我给大家准备了详细的学习资料，微信公众号主页回复“C语言”即可领取。

1. 递归函数

函数自身调用自身的操作，称为函数的递归，递归函数一定要有结束条件，否则会产生死循环。

递归的时候，每次调用一个函数，计算机都会为这个函数分配新的空间，一层一层向内调用；当被调函数返回的时候，调用函数中的变量依然会保持原先的值，这样一层一层进行反向输出。

递归要有两个要素，结束条件与递推关系。

使用递归在解决一些问题时，可以让问题变得简单，降低编程难度。

2. 示例

1. 计算5的阶乘。

#include <stdio.h>

int f(int n)
{
    int result;
    if (n<0){  //判断例外
        printf("input error!\n");
        return 0;
    }else if (n==0 || n==1){
        result = 1;  //结束条件
    }else{
        result = f(n-1) * n;  //递推关系，找公式
    }
    return result;
}

int main(){
    int n;   //输入数字，计算阶乘
    scanf("%d",&n);
    printf("f(%d!)=%d\n",n,f(n));
    return 0;
}

F:\Computer\Project\practice\23\23.3-recursion\cmake-build-debug\23_3_recursion.exe
5
f(5!)=120

进程已结束，退出代码为 0

代码执行过程：

解析：从main函数开始，向内一层一层调用函数，当遇到结束条件，向外一层一层返回执行结果。调用函数的变量保持，和被调函数的返回值的计算结果再向上一层返回。

2. 假如有n个台阶，一次只能上1个台阶或2个台阶，请问走到第n(n为正整数，可自行指定)个台阶有几种走法？

#include <stdio.h>

int step(int n){
    if(1==n || 2==n){  // 结束条件
        return n;
    }
    return step(n-1)+step(n-2);  // 公式
}
int main() {
    int n;
    int ret;
    scanf("%d",&n);  // 输入台阶数
    ret=step(n);
    printf("step total=%d\n", ret);
    return 0;
}

F:\Computer\Project\practice\7\7.2-recursion\cmake-build-debug\7_2_recursion.exe
5
step total=8

进程已结束，退出代码为 0

说明：相较于示例1，示例2就更为复杂一些，使用循环或者排列组合也能解决，但是相当费事。

解析：反着来推，对于上到第n个台阶，要么是从第n-1个台阶上去的，要么是从第n-2个台阶上去的，之前怎么走，不用关心，所有情况都包含在了step(n-1)和step(n-2)的情况里面了。

这种情况是算法中常用的。核心就是找公式，写结束条件。

3. 小结说明

函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N次局部变量、N次形参、N次调用函数地址、N次返回值，势必效率低。

循环能干的事，递归也能干；递归能干的循环不一定能干。

对于我们能用循环解决的，尽量不使用递归。