江小南

V1

2023/01/14阅读:24主题:萌绿

【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函数开始,向内一层一层调用函数,当遇到结束条件,向外一层一层返回执行结果。调用函数的变量保持,和被调函数的返回值的计算结果再向上一层返回。

  1. 假如有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次返回值,势必效率低

循环能干的事,递归也能干;递归能干的循环不一定能干。

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

分类:

后端

标签:

C++

作者介绍

江小南
V1