铁汁们，递归（下）已经更新咯，欢迎铁汁们批评指正。

蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（下）_安然无虞的博客-CSDN博客

目录

一、递归是什么？

二、如何理解“递归”？

1、递归定义

2、递归需要满足的三个条件

3、递归函数

三、怎么玩转递归

1、大招：递归“三段论式”设计经验

2、练习策略

四、精选练习题讲解

1、求n的阶乘

三段论：

代码执行

2、递归求1+2+...+10

三段论

代码执行

3、返回各位数字之和

三段论

代码执行

4、按顺序打印整数i~j

三段论

代码执行

5、对数组arr所有元素求和

三段论

代码执行

五、思考题

六、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿

欢迎回到：遇见蓝桥遇见你，不负代码不负卿！

【声明】：为了让更多的铁汁理解递归，笔者在前面的引入部分赘述可能过长，请铁汁们多点耐心哦，后面有大招。

【前言】：很多人都认为“递归”是语言学习中最难理解的内容之一，当然笔者也是这么认为的，哈哈，但是既然笔者已经将文章发布出来了，自然是有了充分的准备，所以，铁汁们不用紧张，看到最后你会发现，递归其实是一个很自然的东西。

一、递归是什么？

递归是一种应用非常广泛的算法（或者编程技巧）。之后我们要讲的很多数据结构和算法的编码实现都要用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以，搞懂递归非常重要，否则，后面复杂一些的数据结构和算法学起来就会比较吃力。
不过，别看我说了这么多，递归本身可是一点儿都不“高冷”，咱们生活中就有很多用到递归的例子。说一个笔者小时候经常听到的故事：从前有座山，山上有座庙，庙里有个老和尚在讲故事，讲的什么呢，从前有座山...哈哈，这不就是递归吗，只不过是一个无限递归，原因是没有设置终止条件。

举个栗子：周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？
别忘了你是程序员，这个可难不倒你，递归就开始派上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说他在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他自己在哪一排，于是你就知道答案了。
这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：
f(n) = f(n-1) + 1 其中，f(1)=1
f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排数，f(1)=1 表示第一排的人知道自己在第一排。
 

二、如何理解“递归”？

1、递归定义

刘汝佳老师的关于算法竞赛入门经典（紫书）中是这么定义的：

递归：参见“递归”

什么？这个定义什么也没有说啊！好吧，改一下：

递归：如果还是没有明白递归是什么意思，参见“递归”。

奥，也许这次你明白了，原来递归就是自己用到自己的意思。这个定义显然比上一个好些，因为当你终于悟出其中到道理后，就不用继续“参见”下去了。事实上，递归的含义比这个要广泛。

A经理：“这事不归我管，去找B经理。” 于是你去找B经理。

B经理：“这事不归我管，去找A经理。”于是你又回到了A经理这儿。

接下来发生的事就不难想到了。只要两个经理的说辞不变，你有始终听话，你将会永远往返于两个经理之间。这叫做“无限递归”。尽管在这里，A经理并没有让你找他自己，但还是回到了他这儿。换句话说，“间接用到了自己” 也算递归。

回忆一下，在小学的时候，正整数是如何定义的？正整数1,2,3......这些数。这样的定义也许对于小学生来说是没有任何问题的，但当你觉得这样定义“不太严密”时，你或许会喜欢这样的定义：

（1）1是正整数。

（2）如果n是正整数，那么n + 1也是正整数。

（3）只有通过（1）、（2）定义出来的才是正整数。（这里牺牲一点严密性，换来的是更通俗易懂的表达方式）

这样的定义为什么说成是递归呢，因为在“正整数“还没有定义完时，就用到了”正整数”的定义。其实这和前面“参见递归”在本质上是相同的，只是没有它那么直接和明显。

2、递归需要满足的三个条件

究竟什么样的问题可以用递归来解决呢？我总结了三个条件，只要同时满足以下三个条件，就可以用递归来解决。
1. 一个问题的解可以分解为几个子问题的解
何为子问题？子问题就是数据规模更小的问题。比如，前面讲的电影院的例子，你要知道，“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题。
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
比如电影院那个例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。
3. 存在递归终止条件
把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。
 

3、递归函数

数学函数也可以递归定义，例如，阶乘函数f(x) = n! 用递归法编写程序实现如下：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int factor(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (n == 1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return 1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return n * factor(n - 1);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n = 5;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	int ret = factor(n);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("%d\n", ret);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

注意：本题就是简单了解一下用递归写程序是什么样，重点讲解放在后面。

提示：C语言支持递归，即函数可以直接或者间接的调用自己。但是要格外注意为递归函数编写终止条件，否则将产生无限循环。

总结一下：写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

虽然我讲了这么多方法，但是作为初学者，现在是不是还是有种想不太清楚的感觉呢？这也是文章开头我说递归代码比较难理解的原因所在。那怎么办呢，请继续看...
 

三、怎么玩转递归

在重复中找变化，在变化中找重复！

1、大招：递归“三段论式”设计经验

• 找重复-->找子问题
• 找变化-->找重复中的变化量作为参数
• 找边界-->找参数变化趋势设计出口

注意：

1. 对于递归这种折磨人的知识，有人两三天就会了，有人三五年也不会。主要看你悟不悟得透，能不能找到对于递归的感觉。
2. 三段论中的找重复，这个步骤是最重要而且还是最需要感觉的，不过你要相信Practice makes prefect！踏踏实实，多做，多练，多敲。
3. 在找边界设计出口时，最好写在函数的开头。

2、练习策略

• 循环改递归解题
• 经典递归讲解
• 大量练习，总结规律，掌握套路
• 找到感觉，挑战高难度

四、精选练习题讲解

1、求n的阶乘

注意：为了方便大家伙的理解，本题没有考虑n == 0的情况

三段论：

1. 找重复：n * (n - 1)的阶乘，求(n - 1)的阶乘是原问题的重复，规模更小，是原问题的子问题。
2. 找变化：找重复中的变化的量作为参数。本题中很明显是n在变化，所以函数定义过程中的形参是n.
3. 找边界：也就是出口的判断，什么时候让函数停止。显然本题中当n == 1时结束。

代码执行

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //本题中的变化量是n，所以用作形式参数
     
    
   

    

     

    
    

     

      int factor(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//出口的判断，最好写在函数的开头，本题中当n == 1时就意味着到边界了，应该终止程序
     
    
   

    

     

    
    

     
	if (n == 1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return 1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//(n - 1)的阶乘是原问题的重复，是其子问题，规模更小
     
    
   

    

     

    
    

     
	return n * factor(n - 1);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n = 5;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	int ret = factor(5);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("%d\n", ret);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

注意：为了言简意赅，本题中没有考虑n == 0的情况。可能看到这里你还是不能完全理解递归，那么我们应该先理解清楚“上面函数的执行过程”，尤其是，函数执行结束之后，回到调用位置继续往下执行。

注意：建议上面的执行过程，请铁汁们在下面的练习中每一个都画出来，这样你才能清楚地体会到“函数的执行过程”，明白递归的奥秘。

如果仍然无法理解上面的递归，可以作如下比喻。

皇帝（拥有main函数栈帧的男人）：宰相，你给我算一下f(5)。

宰相（拥有f(5)栈帧的男人）：大臣，你给我算一下f(4)。

大臣（拥有f(4)栈帧的男人）：知府，你给我算一下f(3)。

知府（拥有f(3)栈帧的男人）：县令，你给我算一下f(2)。

县令（拥有f(2)栈帧的男人）：师爷，你给我算一下f(1)。

师爷（拥有f(1)栈帧的男人）：回老爷，f(1) = 1。

县令（心算f(2) = 2 * f(1)  = 2）回知府大人，f(2) = 2。

知府（心算f(3) = 3 * f(2) = 6）回大人，f(3) = 6。 

大臣（心算f(4) = 4 * f(3) = 24）回宰相大人，f(4) = 24。

宰相（心算f(5) = 5 * f(4) = 120）回陛下，f(5) = 120。

皇帝满意极了。

虽然这个比喻不甚恰当，但也可以说明一些问题。函数调用时新建了一个栈帧，并且跳转到了函数的开头去执行，就好比皇帝找宰相、宰相找大臣这样的过程。尽管同一时刻可以有多个栈帧（皇帝、宰相、大臣、县令同时处于“等待下级回话”的状态），但是当前代码行只有一个。

铁汁们如果理解了这个比喻，但是不理解调用栈，没关系，它不是本文重点 ，在后面系列的博文中笔者会做详细介绍。你只需要知道递归为什么能正常工作即可。设计递归程序的重点在于上级给下级安排工作。

此时此刻，是补充第一种解题思维——“切蛋糕思维”，最好的时机

如果一时不是很明白，没有关系，后面还有大量的练习让铁汁们体会这个思维的美妙。

2、递归求1+2+...+10

三段论

找重复：求1~(num - 1)是原问题的重复，规模更小，是原题的子问题

找变化：很显然，num是不断变化的，所以函数的形参是num

找边界：num == 1是函数的边界

代码执行

  

   

    

     

    
    

     

      //递归求1+2+3+...+10
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      //很显然num是不断变化的，所以用作函数的形参
     
    
   

    

     

    
    

     

      int sum(int num)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//找边界
     
    
   

    

     

    
    

     
	if (num == 1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return 1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//1~(num - 1)是原问题的重复，规模更小，是原问题的子问题
     
    
   

    

     

    
    

     
	return num + sum(num - 1);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n = 10;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	int ret = sum(n);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("%d\n", ret);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

3、返回各位数字之和

题目描述：输入一个非负整数，返回组成它的数字之和，如输入1729，应该返回1+7+2+9的值，当然1+7+2+9 == 9+2+7+1，也就是19

三段论

找重复：求（num / 10）组成它的数字之和是原问题的重复，规模更小，是其子问题

找变化：num一直在变化

找边界：num < 10 

代码执行

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      int sum(int num)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (num < 10)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return num;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return num % 10 + sum(num / 10);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int num = 1729;
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	printf("%d\n", sum(num));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4、按顺序打印整数i~j

三段论

找重复：（i + 1）是原问题的重复，规模更小，是其子问题

找变化：i 和 j，i在变化不难看出，但为什么要加上j呢，j虽然没有变化，但是i~j这个整体在变，‘i’ 到'j' 的距离不断缩小，所以要加上j来衡量它们二者之间的变化

找边界：当 i > j 时结束

代码执行

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void f2(int i, int j)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (i > j)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("%d ", i);
     
    
   

    

     

    
    

     
	f2(i + 1, j);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	f2(2, 9);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

5、对数组arr所有元素求和

注意：前面内容为了方便更多的铁汁理解，所以笔者选择用C语言编写，但是讲解了4题之后，相信大家对递归都有了一定的认识，数据结构与算法的讲解主要讲的是思路，跟编程语言无关，所以后面的题目笔者选用正在学习中的JAVA语言编写，大家主要听思路，如果听懂了，自己再用熟练的语言编写程序，那么将会事半功倍！

三段论

找重复：求下标begin + 1到arr.length - 1的元素之和是原问题的重复(将首元素的下边设为begin,JAVA中对数组arr求长度直接用arr.length即可)

找变化：begin和剩下的元素都是在变化的，那么如何衡量begin到数组尾元素之间的变化，所以数组名arr也得用作参数

找边界：当begin == arr.legth - 1,也就是当走到尾时结束。

代码执行

  

   

    

     

    
    

     

      public class Recursion {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    public static int f3(int[] arr, int begin) {
     
    
   

    

     

    
    

     
        if(begin == arr.length - 1) {
     
    
   

    

     

    
    

     
            return arr[begin];
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return arr[begin] + f3(arr, begin + 1);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    public static void main(String[] args) {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        int[] arr = {1,3,4,6,7,8,9};
     
    
   

    

     

    
    

     
        int ret = f3(arr, 0);
     
    
   

    

     

    
    

     

              System.out.println(ret);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

注意：加参数也是设计递归的一个难点，有时候我们就想不明白，为什么“切完“之后不知道怎么去写了，比如这一题，如果形参你只给了begin，那么肯定很难用递归去解本题，所以这个时候你就应该想想，是不是缺参数。当然，实在想不出来，可能就应该换种思维了，可能那题不适用”切蛋糕思维“，后面我们会一一介绍。

五、思考题

看过该系列博文的小伙伴都知道，笔者会在博文的最后布置一道思考题，并且讲解上篇博文的思考题。

今天暂时不布置思考题了，但是有任务哦，就是将斐波那契数列和青蛙跳台阶看一下，下篇博文会详细讲解他们用到的另外一种思维。

在讲解上篇思考题的时候，请大家再浏览一遍上篇博文的大致内容，复习巩固一下。

https://blog.csdn.net/weixin_57544072/article/details/120798996utm_source=app&app_version=4.16.0

题：出现K次与出现1次

数组中只有一个数出现1次，其他的数出现了K次，请输出只出现1次的数。

如2,2,2,8,7,7,7,3,3,3

解这样题目的时候，实在不行，就用暴力求解法--》计数即可

但是既然出现在上篇的博文中，那么一定就是让我们使用位运算解决。

讲思路之前，首先大家需要对一个知识点有所了解，那就是：

两个相同的二进制数做不进位加法，结果为0；

十个相同的十进制数做不进位加法，结果为0；

所以有这么一个结论：K个相同的K进制数做不进位加法，结果为0

明白上面那条结论之后，就可以说解决本题的思路了：先将给定的十进制数转化成K进制，再在每个位上做不进位加法，剩下的那个数就是只出现一次的数，不过暂时是K进制的形式，所以再将它还原成十进制数即可。

笔者在这里只给出思路，代码怎么敲，请铁汁们亲自动手实践，用来检测上篇位运算掌握情况。

六、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿

为了让更多的铁汁们能看到这个系列的文章，笔者在这里请求大家动动小手，给笔者来个一键三连，你的支持就是笔者最大的动力，赠人玫瑰，手留余香哦，蟹蟹大家。

铁汁们，递归（下）已经更新咯，快来康康吧。

蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（下）_安然无虞的博客-CSDN博客

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/120836167