理解递归算法的原理

递归算法的概念

递归(Recursion)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法,其核心思想是分治策略。 递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。

关于递归算法

在日常开发中,我们使用循环语句远远大于递归,但这不能说明递归就没有用武之地,实际上递归算法的解决问题的步骤更符合人类解决问题的思路,这是递归算法的优点,同时也是它的缺点。递归算法是比较好用,但是理解起来可能不太好理解,所以在递归算法和循环算法对比中,流行一句话:人理解循环,神理解递归。当然这只是一个段子,不过也从侧面反映出递归算法不容易理解的事实。这个我自己也深有体会,就拿排序算法里面的快排和归并排序来说吧,这两种算法采用的都是分治思想来处理排序问题,所以递归在这里就出现了,如果你不理解递归算法,就去学习这两种排序算法,可能理解起来就非常费事,尽管你知道这两种排序的算法原理和它的时间及空间复杂度,但就是不知道它是如何使用递归完成的,所以学习和理解递归算法是非常有必要的。

实际上递归算法的使用场景,远不止上面说的排序算法,在链表,树,图及其他只要符合分治思想的问题中,其实都可以采用递归来处理。

递归算法的使用

我们先来看一个Java里面,如何写一个最简单的递归方法:

public void recursiveTest(){
    recursiveTest();  //自己调用自己,就叫递归
}

上面就是最简单的递归算法,但不是正确的递归算法,一旦运行起来就会抛出栈内存溢出的异常,因为没有退出条件,所以就会进入死循环中,一直都在重复调用自己,递归调用在底层其实是对线程栈的压栈和出栈操作,每调用一次都会压栈一次,并记录相关的局部变量信息,线程栈的内存是非常有限的,而递归调用如果是无限的,那么很快就会消耗完所有的内存资源,最终导致内存溢出,这一点与空的while死循环是不一样的,单纯的死循环会大量的消耗cpu资源,但不会占用内存资源,所以不会导致程序异常。从这一点能看到递归算法其实是更加消耗系统的性能和资源的,尽管有些编程语言可以做尾递归的优化,降低递归对资源的占用程度,但并不大多数语言都可以支持的或者说很完美的支持,Java就是其中之一,并不支持尾递归的调用。

递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此,在计算机科学中,递归可以被用来描述无限步的运算,尽管描述运算的程序是有限的。 这一点是循环不太容易做到的。

编写正确的递归算法,一定要有 ”归“ 的步骤,也就是说递归算法,在分解问题到不能再分解的步骤时,要让递归有退出的条件,否则就会陷入死循环,最终导致内存不足引发栈溢出异常。

下面,我们通过两个例子来学习一下,递归的使用:

例子一:求阶乘

public static int factrial(int n){
        if(n<1){
            return 1;
        }
        return  n*factrial(n-1);

    }

上面是网上大多数代码的例子,但是对于初学者来言,是不太友好的,因为看不到太多的细节,所以 我改造了一下,实现的是同样的功能,但有详细的步骤,如下:

public static int factrialDetail(int n){
        if(n<1){
            System.out.println("拆解问题完毕,开始分而治之");
            return 1;
        }
        System.out.println("f("+n+")="+n+" * f("+(n-1)+")");
        int z= n*factrialDetail(n-1);

        System.out.println("f("+n+")="+z);

        return  z;

    }

例如,求5的阶乘,结果输出如下:

f(5)=5 * f(4)
f(4)=4 * f(3)
f(3)=3 * f(2)
f(2)=2 * f(1)
f(1)=1 * f(0)
拆解问题完毕,开始分而治之
f(1)=1
f(2)=2
f(3)=6
f(4)=24
f(5)=120

从上面的步骤我们可以清晰的看到递归算法的第一步是分治,把复杂的大的问题,给拆分成一个一个小问题,直到不能再拆解,通过退出条件retrun,然后再从最小的问题开始解决,只到所有的子问题解决完毕,那么最终的大问题就迎刃而解。上面的打印信息,符合栈数据结构的定义,先进后出,通过把所有的子问题压栈之后,然后再一个个出栈,从最简单的步骤计算,最终解决大问题,非常形象。

如下图:

一阶段,递推分解任务:

二阶段:回归分治任务:

例子二:斐波那契数列

斐波那契数列是一个经典的数列,其数列符合黄金分割比的规律,数列越大,其前一项与后一项的比值,越接近黄金比例。

用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233....

下面看下代码:

public static int fibonacci(int n){
        if(n<0){
            throw new IllegalArgumentException("传入参数不合法");
        }
        if(n<=2) {
            return 1;
        };
        //先计算第一个递归函数.
        int plusItem1=fibonacci(n-1);
        int plusItem2=fibonacci(n-2);
        int sum=plusItem1+plusItem2;

        return sum;

    }

注意上面的代码,是我特意改造过的,并没有直接在返回处相加两个递归函数,而是通过存储到变量之后,在最终返回,这样做的目的,是帮助大家更容易理解递归的运行特点:上面这段代码相比阶乘的例子,稍微复杂了点,因为方法体里面出现了两个递归调用函数,而阶乘的只有一个。

int sum=plusItem1+plusItem2;

注意这段代码,一定是在分解任务不能再分解的时候,才开始执行,在不能再分解的时候,就意味着该出栈了,这样一来sum的值,会由两个递归函数的结果汇总,然后向上不断的回报并出栈,直到解决顶层的大问题。

如果不理解的同学,可以传入小一点的参数,然后自己可以试着在纸上划一划,关于递归算法的使用,网上还有比较经典的汉诺塔游戏的解法,此外,如果想练手的同学,可以尝试编写一个十进制转其他进制的递归算法。

总结:

本文主要介绍了递归算法的概念和思想原理及使用例子,递归算法在解决特定场景下的问题非常强大,递归算法的使用,关键在于如何把大问题给分解成相同类型的子问题,然后对一个一个子问题各自击破,当所有的子问题都解决了,那么大的问题也就解决了。最后,使用递归算法需要记住,一定要有让递归回归的约束条件,这才是正确编写递归的前提。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-10-14

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列5

一、是否可以继承String类? String类是final类故不可以继承。 二、面向对象的特征有哪些方面 1.抽象: 抽象就是忽略一个主题中与当前目标无关的...

35950
来自专栏Crossin的编程教室

【Python 第55课】 正则表达式(1)

今天来挖个新坑,讲讲正则表达式。 什么是正则表达式?在回答这个问题之前,先来看看为什么要有正则表达式。 在编程处理文本的过程中,经常会需要按照某种规则去查找一些...

28570
来自专栏Lambda

JavaScript排序算法详解

JS家的排序算法 引子 有句话怎么说来着: 雷锋推倒雷峰塔,Java implements JavaScript. 当年,想凭借抱Java大腿火一把...

32180
来自专栏cs

递归算法

据说凡是可以循环的步骤,都可以递归表示出来。 递归的关键有二点: 1.0 递归公式,即递推式。 2.0 递归出口。 ---- 递归求数组的和 package...

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

P2375 动物园

题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决...

28760
来自专栏marsggbo

(原创)详解KMP算法

KMP算法应该是每一本《数据结构》书都会讲的,算是知名度最高的算法之一了,但很可惜,我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的...

27670
来自专栏HTML5学堂

算法之旅 | 冒泡排序法

HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

41490
来自专栏前端说吧

JS-几大排序算法(更新中...)

46550
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

31240
来自专栏我和我大前端的故事

数据结构学习☞入门(一)算法数据结构

编程如果只是一个为了解决生活温饱的工具,那你可以完全忽略数据结构,算法,你的目标很容易实现;但如果你是热爱编程,把它当做对生活的追求,想在这一行走的更远,更久,...

11130

扫码关注云+社区

领取腾讯云代金券