关于C语言函数递归的详细介绍

我会带着你远行 2023-09-27 22:52 99阅读 0赞

## 递归函数的概念 ##

**递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用自身，每调用一次就进入新的一层**。

举一个求阶乘fact(n)函数的例子

#include<stdio.h>fact
    int fact(int n){//使用递归想法求阶乘 
    	if(n==1||n==0){
    		return 1;
    	}
    	else{
    		return n*fact(n-1); 
    	}
    }
    int main(){
    	int n;
    	//输入所要求的阶乘n
    	scanf("%d",&n);
    	int factn = fact(n);//调用函数求n的阶乘
    	printf("%d的阶乘是:%d",n,factn);
    	
    	return 0; 
    }

![bd53c5484bdb47e9b55acbef99e03b21.png][]

fact(n)函数中出现了新调用方法，即fact(n)函数中再次调用了fact(n-1) ,这种函数自己调用自己的形式称为函数的递归调用。

下面给出调用**过程原理**：

![c9ce1ecdab52462f81c8d139cb5c3cf7.jpeg][]

可以看出**fact(4)**依赖**fact(3)**的值，所以必须先计算出f**act(3)**的值，当**fact(4)**调用自己计算**fact(3)**时，**fact(4)并未结束**，而是暂停一下，等算出**fact(3)**后再计算**fact(4)**,这时计算机内部main()、**fact(4)**和**fact(3)**这3个函数同时执行，**fact(3)**是**fact(4**)的克隆体，尽管程序代码，变量名相同，但属于不同的函数体，不同的参数，不同的变量。这样依次递归，当调用到**fact(1)**时，同时有5个函数运行着，各个克隆体fact()均未结束，**只有当n=1，fact(1)=1时，不必在递归下去。有了函数fact(1)的确切值，就可以计算fact(2),不断退回，不断结束原来的函数，最后可以计算出fact(4);返回到主函数main。**

**从实现过程上看，fact()不断调用自己，如果没有终结的话会发生死机，就像循环没用终止条件会发生死循环一样。所以任何递归函数都必须包含条件来判断是否要递归下去，一旦结束条件成立，递归克隆应该不再继续，以递归出口值作为函数结果，然后返回，结束一个递归克隆函数体，通过一层层返回，一层层计算出i!(i=1,2,3...n-1),最终计算出n!.**

### 递归程序设计与实现 ###

从递归函数的程序编写来看，必须抓住以下两个关键点

**(1)递归出口:即递归结束条件，到何时不再递归下去。**

**(2)递归式子:递归表达式，如：return n\*fact(n-1);**

举一个十进制转化二进制的程序的例子

#include <stdio.h>
    
    void dectobin( int n );
    
    int main()
    {
        int n;
        
        scanf("%d", &n);
        dectobin(n);
        
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    void dectobin( int n )
    {
    	int temp=0;
        if(n==0){
            printf("0");
        }
        else if(n==1){
            printf("1");
        }
        else{
            dectobin(n/2);
            printf("%d",n%2);
            temp++;
        }
    }

![1891dcdde2234c97b4ebb7be011fb530.png][]

刚好巧妙的利用递归原理实现了每一位的输出。

这就是关于递归的理解

[bd53c5484bdb47e9b55acbef99e03b21.png]: https://img-blog.csdnimg.cn/bd53c5484bdb47e9b55acbef99e03b21.png
[c9ce1ecdab52462f81c8d139cb5c3cf7.jpeg]: https://img-blog.csdnimg.cn/c9ce1ecdab52462f81c8d139cb5c3cf7.jpeg
[1891dcdde2234c97b4ebb7be011fb530.png]: https://img-blog.csdnimg.cn/1891dcdde2234c97b4ebb7be011fb530.png