写给小白看的递归(硬核)

大家好，我是bigsai，之前有老弟说弄不懂递归，今天给大家讲讲递归。

创新互联公司是专业的费县网站建设公司，费县接单;提供成都网站制作、网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行费县网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

什么是递归?

递归：就是函数自己调用自己。子问题须与原始问题为同样的事，或者更为简单。

递归通常可以简单的处理子问题，但是不一定是最好的解决方式。

对于递归要分清以下概念：

  • 递归是自己调用自己
  • 递归通常不在意具体操作，只关心初始条件、结束条件和上下层的变化关系。
  • 递归函数需要有临界停止点(结束条件)，即递归不能无限制的执行下去。通常这个点为必须经过的一个数。
  • 递归可以被栈替代。有些递归可以优化。比如遇到重复性的可以借助空间内存记录而减少递归的次数

认识递归，递归函数通常看起来简易但是对于初学者可能很难去理解它，拿一个递归函数来说。

 
 
 
 
      
  
  
  
  1. static void digui() 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     System.out.println("bigsai前"); 
    4.   
  
  
  
  4.     digui(); 
    5.   
  
  
  
  5.     System.out.println("bigsai后"); 
    6.   
  
  
  
  6. } 
    7.

这是一个递归嘛?不是正常递归，没有结束条件，自己一致调用自己导致无限循环。

那正确的递归应该这样

 
 
 
 
      
  
  
  
  1. static void digui(int time) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if(time==0) {}//time==0不执行 
    4.   
  
  
  
  4.     else { 
    5.   
  
  
  
  5.         System.out.println("bigsai前time: "+time); 
    6.   
  
  
  
  6.         digui(time-1); 
    7.   
  
  
  
  7.         System.out.println("bigsai后time: "+time);    
    8.   
  
  
  
  8.     }    
    9.   
  
  
  
  9. } 
    10.

对于这样一种递归，它的流程大致是这样的

 
 
 
 
      
  
  
  
  1. 定义递归算法及参数 
    2.   
  
  
  
  2. - 停止递归算法条件 
    3.   
  
  
  
  3. - (可存在)其他逻辑 
    4.   
  
  
  
  4. - 递归调用(参数需要改变) 
    5.   
  
  
  
  5. - (可存在)其他逻辑 
    6.

所以，调用digui(5)在控制台输出是这样的

那么，我想你对递归函数执行的流程应该有所了解了吧。

递归求阶乘

初学递归，接触最多的就是递归求阶乘，为啥阶乘可以用递归来求呢? 我们首先看下阶乘，n的阶乘表示为：

n!=n*(n-1)*……*1

n的阶乘就是从1开始叠乘到n，那么n-1的阶乘为：

(n-1)!=(n-1)*(n-2)*……*1

通过观察就能知道n的阶乘和n-1的阶乘有这样的关系：

n!=n!=n*(n-1)!

所以，我们要求n的阶乘，我们知道n-1的阶乘乘以n就可以得到，这就是最核心的关系。

0的阶乘为1，通过阶乘上下级的关系，我们假设一个函数jiecheng(n)为求n的阶乘的函数，那么这个函数为：

 
 
 
 
      
  
  
  
  1. static int jiecheng(int n) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if(n==0)//0的阶乘为1 
    4.   
  
  
  
  4.     { 
    5.   
  
  
  
  5.         return 1; 
    6.   
  
  
  
  6.     } 
    7.   
  
  
  
  7.     else { 
    8.   
  
  
  
  8.         return n*jiecheng(n-1);//return n*(n-1)*jiecheng(n-2)=------- 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10. } 
    11.

运行流程为这样：

递归求斐波那契

斐波那契数列，已经跟随我们成长很久很久了，除了直接的斐波那契，爬楼梯等问题也和斐波那契问题差不多。

首先，求斐波那契的公式为：

F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)

也就是除了n=1和2特殊以外，其他均是可以使用递推式，按照上述递归思想，我们假设求斐波那契设成F(n);

那么递推实现的代码为：

 
 
 
 
      
  
  
  
  1. static long F(int n) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if(n==1||n==2) {return 1;} 
    4.   
  
  
  
  4.     else { 
    5.   
  
  
  
  5.         return F(n-1)+F(n-2); 
    6.   
  
  
  
  6.     } 
    7.   
  
  
  
  7. } 
    8.

其实它的调用流程为：

不过这个斐波那契这样的求法效率并不高，后面会提一嘴。

递归解决汉诺塔

汉诺塔是经典递归问题：

  • 相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

  1. 如果A只有一个(A->C)
  2. 如果A有两个(A->B),(A->C),(B->C)
  3. 如果A有三个(A->C),(A->B),(C->B),(A->C),(B->A),(B->C),(A->C).
  4. 如果更多，那么将会爆炸式增长。

可以发现每增加一步，其中的步骤会多很多，如果一步步想，很难想明白，所以要用递归全局的想法看问题。

当有1个要从A->C时，这里使用函数move(A,C)表示(其他move操作同理)。

用hannuo(n)函数表示总共n个盘子要从A->C。

递归，其实就是要找上下层的关系，n个盘子从A挪到C和n-1个盘子从A挪到C有啥联系(hannuo(n)—>hannuo(n-1)有啥关系)。下面带你一步步分析。

假设有n个盘子

hannuo(n-1)之后n-1个盘子从A—>C.

此时剩下底下最大的，只能移动到B，move(A,B)

那么你是否发现什么眉目了，只需原先的huannuo(n-1)相同操作从C—>B即可完成转移到B，所以这个需要加参数表示其方向性，那么我们的之前函数应该写成hannuo(n-1,A,C),但是这里肯定又用到B(向下需要用到)，所以把B传进来hannuo(n-1,A,B,C)先表示为从n-1个从A(借助B执行若干操作)转到C。

这一系列操作使得将n个盘子从A—>B但是我们要的是A—>C才是需要的hannuo(n,A,B,C)，这个很容易啊我们只需要第一步将n-1挪到B上就可以了啊。

经过上面分析，那么完整的操作为：

 
 
 
 
      
  
  
  
  1. package 递归; 
    2.   
  
  
  
  2. public class hannuota { 
    3.   
  
  
  
  3.     static void move(char a,char b) 
    4.   
  
  
  
  4.     { 
    5.   
  
  
  
  5.         System.out.println("移动最上层的"+ a+ "到"+ b+ "\t"); 
    6.   
  
  
  
  6.     } 
    7.   
  
  
  
  7.     static void hannuota(int n,char a,char b,char c)//主要分析每一大步对于下一步需要走的。 
    8.   
  
  
  
  8.     { 
    9.   
  
  
  
  9.         if(n==1) {move(a,c);}//从a移到c 
    10.   
  
  
  
  10.         else 
    11.   
  
  
  
  11.         { 
    12.   
  
  
  
  12.             hannuota(n-1,a,c,b);//将n-1个从a借助c移到b 
    13.   
  
  
  
  13.             move(a,c); //将第n（最后一个）从a移到c。 
    14.   
  
  
  
  14.             hannuota(n-1,b,a,c);//再将n-1个从b借助a移到c 
    15.   
  
  
  
  15.         } 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17.     public static void main(String[] args) 
    18.   
  
  
  
  18.     { 
    19.   
  
  
  
  19.  
    20.   
  
  
  
  20.         hannuota(5,'a','b','c'); 
    21.   
  
  
  
  21.     } 
    22.   
  
  
  
  22. } 
    23.

这样，汉诺塔问题是不是搞懂了?

递归 VS 记忆化

很多时候，递归的效率是很低的(一个递归拆分成两个及以上子问题效率就不太行了)，我们要用动态规划或者记忆化去优化，为什么要记忆化?因为递归成子问题，子问题再拆分成子问题，造成很多的重复计算!

比如上面说到的递归求斐波那契数列，就是一个效率非常低的算法，比如你看看F(5)是这样走的：

在递归求F(4)时候，F(4)递归会求解F(3)，但是右侧的还会再执行一遍。如果是数量非常大的数，那么将耗费很大的时间。所以我们就可以采取记忆化!第一次算出结果的时候就存储一下，如果是线性有规律(大部分)就用数组，否则就用HashMap存储。

具体实现的代码为:

 
 
 
 
      
  
  
  
  1. static long F(int n,long record[]) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.   if(n==1||n==2) {return 1;} 
    4.   
  
  
  
  4.   if(record[n]>0) 
    5.   
  
  
  
  5.     return record[n]; 
    6.   
  
  
  
  6.   else 
    7.   
  
  
  
  7.     record[n]=F(n-1,record)+F(n-2,record); 
    8.   
  
  
  
  8.   return record[n]; 
    9.   
  
  
  
  9. } 
    10.   
  
  
  
  10. public static void main(String[] args) { 
    11.   
  
  
  
  11.   int n=6; 
    12.   
  
  
  
  12.   long[] record = new long[n+1]; 
    13.   
  
  
  
  13.   System.out.println(F(n,record)); 
    14.   
  
  
  
  14. } 
    15.

这样可以节省很多时间，尤其是n非常大的情况(递归是指数级别增长，记忆化是线性级别)。例如一个F(6)求解过程：

当然，记忆化的问题远远不止这么多，具体还需要自行学习。

递归 VS 数据结构

递归在很多场景都有很好的应用，在链表中、二叉树、图中(搜索算法)都有很多的应用，这里就举一些非常经典的例子。

比如在链表中，很经典的就是链表逆序输出、链表反转问题，比如链表反转问题，对应力扣206(给你单链表的头节点 head ，请你反转链表，并返回反转后的链表)，可以这样巧妙的实现：

 
 
 
 
      
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * Definition for singly-linked list. 
    3.   
  
  
  
  3.  * public class ListNode { 
    4.   
  
  
  
  4.  *     int val; 
    5.   
  
  
  
  5.  *     ListNode next; 
    6.   
  
  
  
  6.  *     ListNode() {} 
    7.   
  
  
  
  7.  *     ListNode(int val) { this.val = val; } 
    8.   
  
  
  
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } 
    9.   
  
  
  
  9.  * } 
    10.   
  
  
  
  10.  */ 
    11.   
  
  
  
  11. class Solution { 
    12.   
  
  
  
  12.     public ListNode reverseList(ListNode head) { 
    13.   
  
  
  
  13.         if(head==null||head.next==null) 
    14.   
  
  
  
  14.             return  head; 
    15.   
  
  
  
  15.         ListNode node =reverseList(head.next);//返回最后的链表节点 
    16.   
  
  
  
  16.         head.next.next=head;//后一个节点指向自己 
    17.   
  
  
  
  17.         head.next=null;//自己next指向null  
    18.   
  
  
  
  18.         return node; 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20. } 
    21.

对于二叉树，最经典的就是二叉树的前序、中序、后序遍历的递归实现方式：

例如二叉树前序遍历：

 
 
 
 
      
  
  
  
  1. public void qianxu(node t)// 前序递归 前序遍历：根结点 ---> 左子树 ---> 右子树 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (t != null) { 
    4.   
  
  
  
  4.         System.out.print(t.value + " ");// 当前节点 
    5.   
  
  
  
  5.         qianxu(t.left); 
    6.   
  
  
  
  6.         qianxu(t.right); 
    7.   
  
  
  
  7.     } 
    8.   
  
  
  
  8. } 
    9.

二叉树中序遍历：

 
 
 
 
      
  
  
  
  1. public void zhongxu(node t)// 中序遍历 中序遍历：左子树---> 根结点 ---> 右子树 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (t != null) { 
    4.   
  
  
  
  4.         zhongxu(t.left); 
    5.   
  
  
  
  5.         System.out.print(t.value + " ");// 访问完左节点访问当前节点 
    6.   
  
  
  
  6.         zhongxu(t.right); 
    7.   
  
  
  
  7.     } 
    8.   
  
  
  
  8. } 
    9.

二叉树的后序遍历：

 
 
 
 
      
  
  
  
  1. public void houxu(node t)// 后序遍历 后序遍历：左子树 ---> 右子树 ---> 根结点 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (t != null) { 
    4.   
  
  
  
  4.         houxu(t.left); 
    5.   
  
  
  
  5.         houxu(t.right); 
    6.   
  
  
  
  6.         System.out.print(t.value + " "); // 访问玩左右访问当前节点 
    7.   
  
  
  
  7.     } 
    8.   
  
  
  
  8. } 
    9.

递归 VS 常见算法在我们熟知很多算法都与递归有着很大关系。比如dfs深度优先遍历、回溯算法、分治算法等，这里只是简单介绍一下。

递归只是计算机执行一种方式，一个来回的过程，所以这个过程可以被一些算法很巧妙的运用。

分治算法：将问题分解成多个子问题，子问题求解完合并得到结果，这个过程可以使用递归实现(也可能不使用递归)，但大部分会用递归因为实现更加简洁，它和斐波那契递归不同的是它分裂的子问题一般没有重复的(即分完为止而不会重复计算)。常见的快排、归并排序都是使用分治算法，其算法实现借助递归。例如归并排序其流程：

算法实现为：

 
 
 
 
      
  
  
  
  1. private static void mergesort(int[] array, int left, int right) { 
    2.   
  
  
  
  2.   int mid=(left+right)/2; 
    3.   
  
  
  
  3.   if(left  
  
  
  
  4.   { 
    5.   
  
  
  
  5.     mergesort(array, left, mid); 
    6.   
  
  
  
  6.     mergesort(array, mid+1, right); 
    7.   
  
  
  
  7.     merge(array, left,mid, right); 
    8.   
  
  
  
  8.   } 
    9.   
  
  
  
  9. } 
    10.   
  
  
  
  10.  
    11.   
  
  
  
  11. private static void merge(int[] array, int l, int mid, int r) { 
    12.   
  
  
  
  12.   int lindex=l;int rindex=mid+1; 
    13.   
  
  
  
  13.   int team[]=new int[r-l+1]; 
    14.   
  
  
  
  14.   int teamindex=0; 
    15.   
  
  
  
  15.   while (lindex<=mid&&rindex<=r) {//先左右比较合并 
    16.   
  
  
  
  16.     if(array[lindex]<=array[rindex]) 
    17.   
  
  
  
  17.     { 
    18.   
  
  
  
  18.       team[teamindex++]=array[lindex++]; 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20.     else {                 
    21.   
  
  
  
  21.       team[teamindex++]=array[rindex++]; 
    22.   
  
  
  
  22.     } 
    23.   
  
  
  
  23.   } 
    24.   
  
  
  
  24.   while(lindex<=mid)//当一个越界后剩余按序列添加即可 
    25.   
  
  
  
  25.   { 
    26.   
  
  
  
  26.     team[teamindex++]=array[lindex++]; 
    27.   
  
  
  
  27.  
    28.   
  
  
  
  28.   } 
    29.   
  
  
  
  29.   while(rindex<=r) 
    30.   
  
  
  
  30.   { 
    31.   
  
  
  
  31.     team[teamindex++]=array[rindex++]; 
    32.   
  
  
  
  32.   }     
    33.   
  
  
  
  33.   for(int i=0;i  
  
  
  
  34.   { 
    35.   
  
  
  
  35.     array[l+i]=team[i]; 
    36.   
  
  
  
  36.   } 
    37.   
  
  
  
  37.  
    38.   
  
  
  
  38. } 
    39.

dfs、回溯法 通常想着枚举尽可能多的情况,很多时候我们并不能很好知道运行界限是在哪，并且运行中状态可能会有所变化，所以我们可以写好限定条件使用递归去实现，递归的归过程也可很好的复原去进行其他试探。包括二叉树的前中后遍历都蕴涵dfs算法思想,而回溯算法则是经典全排列、八皇后问题代表。

其流程通常为：

 
 
 
 
      
  
  
  
  1. 定义回溯算法及参数 
    2.   
  
  
  
  2. - (符合条件)跳出 
    3.   
  
  
  
  3. - (不符合)不跳出： 
    4.   
  
  
  
  4. - - 遍历需要操作的列表&&该元素可操作&&可以继续试探 
    5.   
  
  
  
  5. - - - 标记该元素已使用以及其他操作 
    6.   
  
  
  
  6. - - - 递归调用(参数改变) 
    7.   
  
  
  
  7. - - - 清除该元素标记以及其他操作 
    8.

此外，递归还在很多算法中有广泛的应用，这里就不具体列举啦!

结语

今天递归就讲到这里啦，学好递归没那么容易，还是要具体掌握各种算法、题目才能慢慢领略递归精髓，递归用好可以写出很多骚代码!

不过实际题目注重效率和便捷，不能盲目追求效率，也不能盲目使用递归不注意算法优化。

本文标题：写给小白看的递归(硬核)
网站URL：http://www.mswzjz.cn/qtweb/news38/530088.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能

贝锐智能技术为您推荐以下文章

网站排名知识

行业网站建设

成都圣月服饰　　 　联通机房服务器托管　　 　香港空间　　 　西部信息服务器托管　　 　温江做网站　　 　wap手机网站　　 　广安搬家公司　　 　网络营销推广　　 　双流能亿建站　　 　中建建业环保　　 　成都网站制作　　 　支点广告　　 　香港虚拟主机腾讯云　　 　玄科环保　　 　成都网站营销　　 　成都楼顶广告牌　　 　成都标识标牌设计制作　　 　成都未宇聚　　 　成都网站优化　　 　成都茶叶销售