递归就这么简单

递归介绍

本来预算此章节是继续写快速排序的,然而编写快速排序往往是递归来写的,并且递归可能不是那么好理解,于是就有了这篇文章。

在上面提到了递归这么一个词,递归在程序语言中简单的理解是:方法自己调用自己

递归其实和循环是非常像的,循环可以改写成递归,递归未必能改写成循环,这是一个充分不必要的条件。

  • 那么,有了循环,为什么还要用递归呢??在某些情况下(费波纳切数列,汉诺塔),使用递归会比循环简单很多很多
  • 话说多了也无益,让我们来感受一下递归吧。

我们初学编程的时候肯定会做过类似的练习:

  • 1+2+3+4+....+100(n)求和
  • 给出一个数组,求该数组内部的最大值

我们要记住的是,想要用递归必须知道两个条件:

  • 递归出口(终止递归的条件)
  • 递归表达式(规律)

技巧:在递归中常常是将问题切割成两个部分(1和整体的思想),这能够让我们快速找到递归表达式(规律)

一、求和

如果我们使用for循环来进行求和1+2+3+4+....+100,那是很简单的:

    int sum = 0;
    for (int i = 1; i <= 100; i++) {

        sum = sum + i;

    }
    System.out.println("公众号:Java3y:" + sum);

前面我说了,for循环都可以使用递归来进行改写,而使用递归必须要知道两个条件:1、递归出口,2、递归表达式(规律)

首先,我们来找出它的规律:1+2+3+...+n,这是一个求和的运算,那么我们可以假设X=1+2+3+...+n,可以将1+2+3+...+(n-1)看成是一个整体。而这个整体做的事又和我们的初始目的(求和)相同。以我们的高中数学知识我们又可以将上面的式子看成X=sum(n-1)+n

好了,我们找到我们的递归表达式(规律),它就是sum(n-1)+n,那递归出口呢,这个题目的递归出口就有很多了,我列举一下:

  • 如果n=1时,那么就返回1
  • 如果n=2时,那么就返回3(1+2)
  • 如果n=3时,那么就返回6(1+2+3)

当然了,我肯定是使用一个最简单的递归出口了:if(n=1) return 1

递归表达式和递归出口我们都找到了,下面就代码演示:

递归出口为1:

    public static void main(String[] args) {
        System.out.println("公众号:Java3y:" + sum(100));
    }

    /**
     *
     * @param n 要加到的数字,比如题目的100
     * @return
     */
    public static int sum(int n) {

        if (n == 1) {
            return 1;
        } else {
            return sum(n - 1) + n;
        }
    }

递归出口为4:

    public static void main(String[] args) {
        System.out.println("公众号:Java3y:" + sum(100));
    }

    /**
     *
     * @param n 要加到的数字,比如题目的100
     * @return
     */
    public static int sum(int n) {

        //如果递归出口为4,(1+2+3+4)
        if (n == 4) {
            return 10;
        } else {
            return sum(n - 1) + n;
        }
    }

结果都是一样的。

二、数组内部的最大值

如果使用的是循环,那么我们通常这样实现:

    int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};

    //将数组的第一个假设是最大值
    int max = arrays[0];

    for (int i = 1; i < arrays.length; i++) {

        if (arrays[i] > max) {
            max = arrays[i];
        }
    }

    System.out.println("公众号:Java3y:" + max);

那如果我们用递归的话,那怎么用弄呢?首先还是先要找到递归表达式(规律)和递归出口

  • 我们又可以运用1和整体的思想来找到规律
    • 将数组第一个数->2与数组后面的数->{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}进行切割,将数组后面的数看成是一个整体X={3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2},那么我们就可以看成是第一个数和一个整体进行比较if(2>X) return 2 else(2<X) return X
    • 而我们要做的就是找出这个整体的最大值与2进行比较。找出整体的最大值又是和我们的初始目的(找出最大值)是一样的
    • 也就可以写成if( 2>findMax() )return 2 else return findMax()
  • 递归出口,如果数组只有1个元素时,那么这个数组最大值就是它了。

使用到数组的时候,我们通常为数组设定左边界和右边界,这样比较好地进行切割

  • L表示左边界,往往表示的是数组第一个元素,也就会赋值为0(角标为0是数组的第一个元素)
  • R表示右边界,往往表示的是数组的长度,也就会赋值为arrays.length-1(长度-1在角标中才是代表最后一个元素)

那么可以看看我们递归的写法了:

  public static void main(String[] args) {

        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};

        System.out.println("公众号:Java3y:" + findMax(arrays, 0, arrays.length - 1));


    }


    /**
     * 递归,找出数组最大的值
     * @param arrays 数组
     * @param L      左边界,第一个数
     * @param R      右边界,数组的长度
     * @return
     */

    public static int findMax(int[] arrays, int L, int R) {

        //如果该数组只有一个数,那么最大的就是该数组第一个值了
        if (L == R) {
            return arrays[L];
        } else {

            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);//找出整体的最大值

            if (a > b) {
                return a;
            } else {
                return b;
            }
        }

    }

三、冒泡排序递归写法

在冒泡排序章节中给出了C语言的递归实现冒泡排序,那么现在我们已经使用递归的基本思路了,我们使用Java来重写一下看看:

冒泡排序:俩俩交换,在第一趟排序中能够将最大值排到最后面,外层循环控制排序趟数,内层循环控制比较次数

以递归的思想来进行改造:

  • 当第一趟排序后,我们可以将数组最后一位(R)和数组前面的数(L,R-1)进行切割,数组前面的数(L,R-1)看成是一个整体,这个整体又是和我们的初始目的(找出最大值,与当前趟数的末尾处交换)是一样的
  • 递归出口:当只有一个元素时,即不用比较了:L==R
    public static void main(String[] args) {

        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};
        bubbleSort(arrays, 0, arrays.length - 1);
        System.out.println("公众号:Java3y:" + arrays);


    }

    public static void bubbleSort(int[] arrays, int L, int R) {

        int temp;

        //如果只有一个元素了,那什么都不用干
        if (L == R) ;

        else {
            for (int i = L; i < R; i++) {
                if (arrays[i] > arrays[i + 1]) {
                    temp = arrays[i];
                    arrays[i] = arrays[i + 1];
                    arrays[i + 1] = temp;
                }
            }

            //第一趟排序后已经将最大值放到数组最后面了

            //接下来是排序"整体"的数据了
            bubbleSort(arrays, L, R - 1);

        }
    }

四、斐波那契数列

接触过C语言的同学很可能就知道什么是费波纳切数列了,因为往往做练习题的时候它就会出现,它也是递归的典型应用。

菲波那切数列长这个样子:{1 1 2 3 5 8 13 21 34 55..... n }

数学好的同学可能很容易就找到规律了:前两项之和等于第三项

例如:

     1 + 1 = 2
    2 + 3 = 5
    13 + 21 = 34

如果让我们求出第n项是多少,那么我们就可以很简单写出对应的递归表达式了:Z = (n-2) + (n-1)

递归出口在本题目是需要有两个的,因为它是前两项加起来才得出第三项的值

同样地,那么我们的递归出口可以写成这样:if(n==1) retrun 1 if(n==2) return 2

下面就来看一下完整的代码吧:

    public static void main(String[] args) {

        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);

        int fibonacci = fibonacci(10);
        System.out.println("公众号:Java3y:" + fibonacci);


    }

    public static int fibonacci(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        } else {
            return (fibonacci(n - 1) + fibonacci(n - 2));
        }

    }

五、汉诺塔算法

图片来源百度百科:

玩汉诺塔的规则很简单:

  • 有三根柱子,原始装满大小不一的盘子的柱子我们称为A,还有两根空的柱子,我们分别称为B和C(任选)
  • 最终的目的就是将A柱子的盘子全部移到C柱子中
    • 移动的时候有个规则:一次只能移动一个盘子,小的盘子不能在大的盘子上面(反过来:大的盘子不能在小的盘子上面)

我们下面就来玩一下:

  • 只有一个盘子:
    • A柱子的盘子直接移动到C柱子中
    • 完成游戏
  • 只有两个盘子:
    • 将A柱子上的盘子移动到B柱子中
    • 将A柱子上的盘子移动到C柱子中
    • 最后将在B柱子的盘子移动到C柱子盘子中
    • 完成游戏
  • 只有三个盘子:
    • 将A柱子的盘子移动到C柱子中
    • 将A柱子上的盘子移动到B柱子中
    • 将C柱子盘子移动到B柱子盘子中
    • 将A柱子的盘子移动到C柱子中
    • 将B柱子的盘子移动到A柱子中
    • 将B柱子的盘子移动到C柱子中
    • 最后将A柱子的盘子移动到C柱子中
    • 完成游戏

…………………..

从前三次玩法中我们就可以发现的规律:

  • 想要将最大的盘子移动到C柱子,就必须将其余的盘子移到B柱子处(借助B柱子将最大盘子移动到C柱子中[除了最大盘子,将所有盘子移动到B柱子中])[递归表达式]
  • 当C柱子有了最大盘子时,所有的盘子在B柱子。现在的目的就是借助A柱子将B柱子的盘子都放到C柱子中(和上面是一样的,已经发生递归了)
  • 当只有一个盘子时,就可以直接移动到C柱子了(递归出口)
    • A柱子称之为起始柱子,B柱子称之为中转柱子,C柱子称之为目标柱子
    • 从上面的描述我们可以发现,起始柱子、中转柱子它们的角色是会变的(A柱子开始是起始柱子,第二轮后就变成了中转柱子了。B柱子开始是目标柱子,第二轮后就变成了起始柱子。总之,起始柱子、中转柱子的角色是不停切换的)

简单来说就分成三步:

  1. 把 n-1 号盘子移动到中转柱子
  2. 把最大盘子从起点移到目标柱子
  3. 把中转柱子的n-1号盘子也移到目标柱子

那么就可以写代码测试一下了(回看上面玩的过程):

    public static void main(String[] args) {
        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);
        //int fibonacci = fibonacci(10);
        hanoi(3, 'A', 'B', 'C');
        System.out.println("公众号:Java3y" );
    }
    /**
     * 汉诺塔
     * @param n n个盘子
     * @param start 起始柱子
     * @param transfer 中转柱子
     * @param target 目标柱子
     */
    public static void hanoi(int n, char start, char transfer, char target) {
        //只有一个盘子,直接搬到目标柱子
        if (n == 1) {
            System.out.println(start + "---->" + target);
        } else {
            //起始柱子借助目标柱子将盘子都移动到中转柱子中(除了最大的盘子)
            hanoi(n - 1, start, target, transfer);
            System.out.println(start + "---->" + target);
            //中转柱子借助起始柱子将盘子都移动到目标柱子中
            hanoi(n - 1, transfer, start, target);
        }
    }

我们来测试一下看写得对不对:

参考资料:

  • https://www.zhihu.com/question/24385418

六、总结

递归的确是一个比较难理解的东西,好几次都把我绕进去了….

要使用递归首先要知道两件事:

  • 递归出口(终止递归的条件)
  • 递归表达式(规律)

在递归中常常用”整体“的思想,在汉诺塔例子中也不例外:将最大盘的盘子看成1,上面的盘子看成一个整体。那么我们在演算的时候就很清晰了:将”整体“搬到B柱子,将最大的盘子搬到C柱子,最后将B柱子的盘子搬到C柱子中

因为我们人脑无法演算那么多的步骤,递归是用计算机来干的,只要我们找到了递归表达式和递归出口就要相信计算机能帮我们搞掂。

在编程语言中,递归的本质是方法自己调用自己,只是参数不一样罢了。

最后,我们来看一下如果是5个盘子,要运多少次才能运完:

PS:如果有更好的理解方法,或者我理解错的地方大家可以在评论下留言一起交流哦!

本文分享自微信公众号 - Java3y(gh_085b56c42174)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青玉伏案

Objective-C中的内存管理

        在编程语言中是少不了对内存的管理的,内存对于计算机来说是宝贵的资源,所以对使用不到的资源进行回收是很有必要的。OC中使用引用计数和垃圾回收来管理...

19390
来自专栏陈满iOS

iOS开发·NSString字符串的各种基本操作,数值转换及衍生操作

但有时候,仅仅停留在这些基本操作还不能直接满足一些需求,这时候可以利用这些基本操作进行一些字符串的衍生操作。

34220
来自专栏数据结构与算法

6261:汉诺塔问题

6261:汉诺塔问题 总时间限制: 1000ms 内存限制: 65536kB描述 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的...

38850
来自专栏陈满iOS

iOS开发·runtime+KVC实现多层字典模型转换(多层数据:模型嵌套模型,模型嵌套数组,数组嵌套模型)

更重要的是,有时候在iOS面试的时候,部分面试官会不仅问你某种场景会用到什么框架,更会问你如果要你来实现这个功能,你有没有解决思路?所以,自己实现字典转模型还是...

42310
来自专栏IMWeb前端团队

Promise的简单实现

本篇文章通过构建一个简单的Promise对象来了解如何做到异步获得数据。 使用方法 const fetch = function(url) { return...

23590
来自专栏菩提树下的杨过

objective-C中的Class(类类型),Selector(选择器SEL),函数指针(IMP)

今天在园子里看到了一篇牛文“Objective-C 2.0 with Cocoa Foundation--- 5,Class类型,选择器Selector以及函数...

25650
来自专栏C#

C#二进制流的序列化和反序列化

1 public class BinaryHelper 2 { 3 /// <summary> 4 /...

30070
来自专栏菩提树下的杨过

objective-C 的内存管理之-引用计数

obj-c本质就是"改进过的c语言",大家都知道c语言是没有垃圾回收(GC)机制的(注:虽然obj-c2.0后来增加了GC功能,但是在iphone上不能用,因此...

216100
来自专栏青玉伏案

Objective-C中的语法糖

  写这篇博客源于一个疑问:“WoK~, 这也行?!”。刚接触OC不久,今天做深浅拷贝的测试,无意中把获取NSArray的值写成了用下标获取的方式。当时把注意力...

23450
来自专栏Scott_Mr 个人专栏

利用Runtime实现简单的字典转模型

12930

扫码关注云+社区

领取腾讯云代金券