算法|浅谈递归

算法|浅谈递归

Scroll Down

前言

最近在做链表的题,发现链表中很多问题都可以利用递归的方法来解决,本科学算法和数据结构的时候也没咋认真,现在想想还是挺后悔的。因此,想总结一下这个简单好用的思想,以便加深自己的理解。

什么是递归

何为递归呢?要理解递归,就得先了解什么是递归,实际上这句话就是一个递归。这么说可能不好理解,接下来我举个简单的例子来解释这段话的意义。

你的女朋友晚上睡觉,让你给她讲故事,做为工科生的你,肚子里没有那么多墨水,怎么办呢?你灵机一动,开始讲故事。你给你女朋友说,从前有个小伙子,他很喜欢她的女朋友,每天晚上都给他女朋友讲故事。你女朋友就问你了,那他讲的什么故事呢?你从容的回答到,他讲的是一个小伙子,他很喜欢她的女朋友,每天晚上都给他女朋友讲故事。当然,如果你的女朋友足够聪明,她应该能意识到你在敷衍她了,但是如果你的女朋友没有意识到,觉得这个故事很有趣,就一直听你讲,你就不断的重复这个故事,一遍一遍的讲下去...这个过程就是递归的过程。

递归的条件

想打游戏的你意识到了,我不能给我女朋友一直讲这个无聊的故事吧,什么时候才能停止呢。这就涉及到了一个问题,那就是递归的条件。如果我们不给递归设定一个出口,那么我们的递归就会是死循环,直到你的程序崩溃为止。因此,在进行递归的时候,我们必须给递归设定一个出口,也就是告诉递归什么时候终止。继续拿上面的例子来举例,你不能一直给女朋友重复这个故事,那么你的递归的终止条件就是当女朋友睡着了,你就停止递归,去打游戏,这样就能保证你不崩溃,从而继续的和你的女朋友恩恩爱爱。

举完例子,我们来看看代码。


   /**
     * 求1+2+3+...+n的和
     * @param n
     * @return
     */
    public static int Sum(int n)
    {
        if (n>0)
        {
            n+=Sum(n-1);
        }
        return n;
    }

这个代码想必大家很熟悉,就是高斯小学的时候计算1到100的累加。利用递归,我们可以很方便的得到它的结果。如果我们不给他出口,那么它将栈溢出。
image.png

为什么是栈溢出呢?因为在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。

递归的优缺点

看完上面这个简单的例子,大家也明白了什么是递归了,那递归有哪些优缺点呢?

  • 优点:
  1. 更加优雅的代码
  2. 易于理解
  • 缺点:
  1. 时间和空间的消耗比较大
    递归由于是函数调用自身,而函数的调用时消耗时间和空间的,每一次函数调用,都需要在内存栈中分配空间以保存参数,返回值和临时变量,而往栈中压入和弹出数据也都需要时间,所以降低了效率。

  2. 重复计算
    递归中又很多计算都是重复的,递归的本质时把一个问题分解成两个或多个小 问题,多个小问题存在重叠的部分,即存在重复计算,如斐波那契数列的递归实现。

  3. 调用栈溢出
    递归可能时调用栈溢出,每次调用时都会在内存栈中分配空间,而栈空间的容量是有限的,当调用的次数太多,就可能会超出栈的容量,进而造成调用栈溢出。

任何一个算法,都有着自己的优缺点,毕竟世上安得两全法,哪有时间复杂度又小空间复杂度又小,还能很好的解决问题的算法呢?因此,应当结合实际,来选择是否使用递归。

递归的应用场景

  1. 链表、树的操作
    由于链表和树的数据的结构形式是按递归定义的,结构本身具有递归特性,因此可以使用递归来对其进行操作。如Leetcode的206题链表反转
    image.png
    代码如下:
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode next = head.next;
    ListNode newHead = reverseList(next);
    next.next = head;
    head.next = null;
    return newHead;
}

21题合并两个有序链表
image.png
代码如下:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

采用递归的形式让你的代码更简洁。

  1. 问题按递归定义
    比如Fibonacci数列,阶乘,等差数列求和等。
//Fibonacci数列
public static int factorial(int n){
    if (n <= 1){
            return 1;
    }
    return factorial(n-1) + factorial(n-2);
    }
  1. 问题的解法是递归的
    有些问题只能使用递归(迭代)方法来解决,例如,汉诺塔问题,八皇后问题等
//使用递归法求解含有n个不同大小盘子的汉诺塔移动路径,参数n为盘子数,把A塔上盘子全部移动到C塔上,B为过渡塔
public static void recursionHanoi(int n,char A,char B,char C){
    if(n == 1){
            System.out.print(A+"——>"+C+"\n");    
    }
    else{
            recursionHanoi(n-1,A,C,B);         //使用递归先把A塔最上面的n-1个盘子移动到B塔上,C为过渡塔
            System.out.print(A+"——>"+C+"\n");       //把A塔中底下最大的圆盘,移动到C塔上
            recursionHanoi(n-1,B,A,C);         //使用递归把B塔上n-1个盘子移动到C塔上,A为过渡塔
        }
    }