c语言_递归的简单认识

拼搏现实的明天。 2023-05-21 11:56 11阅读 0赞

c语言的学习中函数递归我们也很常见，那么什么是递归呢？简单来说就是在函数体中自己调用自己，把一般的循环问题转成递归来书写代码，大大减小了代码量(递归代码量看起来虽然少，但是不好想耶，害…），递归的主要思想就是：**大事化小事，一点一点去解决问题**。

递归两要素：**1.子问题的处理方式和父问题一样**(这样才能把问题化小后，依旧能用自身的这个函数去解决)。**2.递归要有出口**(简单来说，当问题小到什么程度的时候，递归就不再继续，就不用再继续化小了，就能直接得出当前小问题的答案)，每次的递归都必须保证越来越接近这个出口。

函数的递归调用，上一层没执行完的函数会先保存在内存的栈上，下一层的函数会先压住上一层的函数，等下一层的函数执行完成之后，返回到上一层的函数，接着执行后面的语句。

下面我们一起来看几个简单的例子吧。

**1.打印整数的每一位**

> 输入：1234  
> 输出：1 2 3 4

思路：大问题是依次打印每一位，我们打印4之前要打印3，打印3之前要打印2，打印2之前要打印1。这不就把大问题变成小问题了吗。我们可以一直对数字进行 /10 递归，直到只剩下一位的时候，我们就打印它，然后递归回到上一层剩两位的时候，我们继续打印它的 %10 结果……这样到最后，我们就依次打印出了整数的每一位。

**思路图解：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70_pic_center]  
**代码如下：**

#include<stdio.h>
    void My_printf(int num)
    { 
    	if(num>9)
    	{ 
    		My_printf(num/10);  //当整数还不是一位的时候，我们继续 /10 递归
    	}
    		
    	printf("%d ",num%10);   
    }
    int main()
    { 
    	int num;
    	scanf("%d",&num);
    	My_printf(num);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70]  
**2.求字符串的长度**

> 输入：abcd  
> 输出：4

思路：字符串以’\\0’结尾，求abcd的长度，就是求1+bcd的长度，求bcd的长度，就是求1+cd的长度，求cd的长度，就是求1+d的长度，求d的长度就是求1+’\\0’的长度，当字符串==’\\0’的时候，返回0。

#include <stdio.h>
    
    int My_Strlen(char*str)
    { 
    	if(*str == '\0')
    	{ 
    		return 0;
    	}
    	
    	return 1+My_Strlen(str+1);
    }
    
    int main()
    { 
    	char p[10];
    	scanf("%s",p);
    	int len = My_Strlen(p);
    	printf("%d\n", len);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70 1]  
**3.求n的阶乘**

> 输入：5  
> 输出：120

思路：求5的阶乘，等于求5 \* 4！，求4！等于求4 \* 3！，求3！等于求3 \* 2！，求2！等于求2 \* 1！，当num==1时，返回1。

#include<stdio.h>
    
    int factorial(int num)
    { 
    	if(num <= 1) //0!是也1
    	{ 
    		return 1;
    	}
    	
    	return num* factorial(num-1);
    }
    int main()
    { 
    	int num;
    	scanf("%d",&num);
    	int ans=factorial(num);
    	printf("%d",ans);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70 2]  
  递归的运用还有很多，一般情况下，我们不应该使用递归，当递归次数很大的时候，递归占用栈空间会很大，容易造成栈溢出，有些时候时间复杂度也会太高，我们一般转换成循环来进行问题的求解。

有些问题我们使用递归解决，看起来会很简洁，用非递归实现效率会更高，但是代码可读性稍微会差一些。当一个问题特别复杂的时候，此时递归实现的简洁性便可以补偿它的运行开销。

越努力，越幸福！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70_pic_center]: /images/20230521/32f87da6375e414ca71f931be43600ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70]: /images/20230521/227160e626954bcdacb7c41915ad62e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230521/4b08c4b4af52408e86531fb50c46f726.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70 1]: /images/20230521/9af62d844699400392e178002e42fb60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230521/d724bd51ec894d60acd9ce5ab6abf687.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW56aGFucGVuZ18_size_16_color_FFFFFF_t_70 2]: /images/20230521/c089347ecf5145b09dbe12b4614e82c6.png