你真的懂递归吗?

什么是递归?

通俗来讲:递归就是方法自己调用自己,通过每次传入的参数不同,可以解决复杂的问题。

为什么需要递归

递归算法可以把本身问题分解规模小的同类问题,通过求解规模小的同类问题的解,之后不断进行返回值,最终可以求得规模大的问题。

来看看递归的优缺点:

优点缺点
1. 逻辑性好;2. 可读性好;3.代码简洁。1. 由于递归需要利用栈,所以占用空间大,可能会发生栈溢出;2. 会存在重复计算,需要进行优化。

递归的三大要素

第一要素: 明确你这个函数想要干什么。先不管函数里面的代码什么,而是要先明白,你这个函数的功能是什么,要完成什么样的一件事。

第二要素: 寻找递归结束条件。我们需要找出当参数为啥时,递归结束,之后直接把结果返回,请注意,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。

第三要素: 找出函数的等价关系式。我们要不断缩小参数的范围,缩小之后,我们可以通过一些辅助的变量或者操作,使原函数的结果不变。

递归的过程

你真的懂递归吗?

上面的递归的过程比较抽象,接下来自己慢慢讲:

需要了解的知识点

栈:栈是一种数据结构,可以实现先进后出的功能。我们写的程序需要调用线程来执行,如下图,通过查看JVM的内存管理模型,可以知道虚拟机栈是线程私有的,其中虚拟机栈的作用就是每次方法调用的数据需要通过栈来传递。

你真的懂递归吗?

递归的调用机制

  1. 利用阶乘问题讲解递归的调用机制:
class Solution{
    public static void main(String[] args){
        int res = factorial(3);
    }
    //第一步,明确函数的功能
    public static int factorial(int n){
        //第二步,递归的结束条件
        if(n == 1){
            return 1;
        }else{
            //第三步,函数的等价关系式
            return factorial(n - 1) * n;
        }
    }
}

图解:方法递归时,实际内存运行过程。
你真的懂递归吗?

需要遵守的规则

  • 执行一个方法时,就会创建一个新的独立栈空间。
  • 方法的局部变量是独立的,不会相互影响,比如程序中的变量n。
  • 如果方法中使用的是引用类型的变量(比如数组),就会共享该引用类型的数据。
  • 递归必须要向退出递归的条件逼近,否则就会无限递归,会出现StackOverflowError
  • 当一个方法执行完毕,或者遇到return,就会返回,遵循谁调用,就将结果返回给谁

实例2:利用递归反转链表

反转链表,如对链表1->2->3->4 进行反转为4->3->2->1

首先定义链表的节点

class Node{
    int val;
    Node next;
}

按照递归的三要素来

第一步:定义函数的功能

设函数reverseLinkedList(head)的功能是反转链表,其中head表示链表的头节点。

Node reverseLinkedList(Node head){
	
}

第二步:递归的结束条件

当链表没有节点或只有一个节点时,此时不用进行反转,这个作为递归的结束条件。

Node reverseLinkedList(Node head){
    if(head == null || head.next == null){
        return head;
    }
}

第三步:寻找等价条件

这个有一定的难度,根据需要遵守的规则,在找等价条件的过程中,一定是要逼近递归的结束条件。

Node reverseLinkedList(Node head){
    if(head == null || head.next == null){
        return head;
    }
    //不断去移动指针,不断去逼近结束条件。
    Node newList = reverseLinkedList(head.next);
}

根据上述求阶乘的例子,可以知道此时的内存运行过程,通过不断地移动指针(head.next),最终只用一个节点,如,通过过程,对于1->2->3->4链表此时为:
你真的懂递归吗?
接下来就是过程了,交换指针的指向。

//用递归的方法反转链表
public static Node reverseList2(Node head){
    // 1.递归结束条件
    if (head == null || head.next == null) {
             return head;
         }
         // 递归反转 子链表
         Node newList = reverseList2(head.next);
         // 改变 3,4节点的指向。
         // 通过 head.next获取节点4
         Node t1  = head.next;
         // 让 4 的 next 指向 4
         t1.next = head;
         // 3 的 next 指向 null.
        head.next = null;
        // 把调整之后的链表返回。
        return newList;
    }

第一次归的过程
你真的懂递归吗?
当归过程结束可实现反转
你真的懂递归吗?

优化

后续。。。

总结

对于初学者来讲,理解递归是比较有难度的,但是只要去了解其中的思想,多做一些练习是可以掌握的。

另外,自己也在学习算法,自己将剑指offer刷完了:

剑指offer

参考

  1. https://baijiahao.baidu.com/s?id=1629571574350179349&wfr=spider&for=pc
  2. https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/jvm/Java内存区域.md
  3. https://www.zhihu.com/question/31412436

相关推荐