特殊的线性表:递归

2019-08-03

特殊的线性表:递归

   介绍完数组和链表,以及两个特殊的线性结构栈和队列后,已经算是迈入了数据结构的门了,后面很多其他更复杂的数据结构都会基于数组和链表来实现,比如散列表、树、图等,有些甚至需要结合数组和链表来实现,在继续介绍后续复杂的数据结构之前,我们穿插进来一些常见的排序算法和查找算法,在系统介绍这些算法之前,我们先来一道前菜:递归。

   递归算不上任何数据结构和算法,但确实是一种很重要的编程技巧,很多算法也会用到递归来实现,比如归并排序、快速排序、二分查找等。

   递归,简单来讲就是在函数定义中调用函数自身,从我们之前学习数学解题经验来讲,就是将一个大的问题拆分成多个小问题,逐一击破后最后归并结果。

   我们判断一个问题是否可以通过递归来解决,主要看它是否满足以下三个条件:

     1、一个问题的解可以分解为几个子问题的解

     2、这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样

     3、存在递归终止条件 递归一定要有终止条件,否则会导致函数被无限调用最终致使内存溢出。

   通过以上分析,我们可以整理出递归代码的编写思路:写出递归公式,找到终止条件。有句话叫做「人理解迭代,神理解递归」,说的就是递归代码可读性不好,理论上看,递归代码都是可以转化成迭代实现的,但是递归代码更简洁,更显逼格,我们在通过递归实现代码的时候,切忌试图通过人脑去分解每个步骤,那样会把自己搞晕的,这种重复迭代的事情交给计算机去做,我们要做的就是抽象出规律,写递归公式,找终止条件,再把它们转化为递归代码,就完事了。

   说了这么多,最后通过一个案例来帮助你去理解和实际运用。递归的应用案例很多,比如经典的汉诺塔、斐波那契数列等,我们以斐波那契数列来演示下递归代码的编写,斐波那契数列是这样一组数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …(你可以去网上搜一下了解下这个数列的现实由来),求第n个数列的值。

   按照我们前面列出的递归问题解题思路,首先抽象出这组数列的一般规律,将其整理成递归公式,会得出如下结论(索引从0开始,即第零项):

     F0 = 0

     F1 = 1

     ...

     F(n) = F(n-1) + F(n-2)

    这样,我们同时有了终止条件和递归公式,接下来,就是将其转化为递归代码了:

<?php
/**
 * 通过递归实现斐波那契数列
 */
function fibonacci($n)
{
    if ($n == 0) {
        return 0;
    }
    if ($n == 1) {
        return 1;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}


print fibonacci(5);  # 5
print fibonacci(8);  # 21

   通过递归,我们用非常简洁的代码就实现了复杂的斐波那契数列的求解,如果要用迭代来实现这个逻辑,不定要写多少代码呢。

   编写递归代码时有两个注意事项,一个是警惕堆栈溢出,为此要设定好终止条件和合理的递归层数,另一个是防止重复计算,因此,递归公式要经过认证求证,不能凭感觉贸然下手编码,不然真的会失之毫厘,谬以千里。

 

特殊的线性表:递归

特殊的线性表:递归

原文地址:https://www.cnblogs.com/mzhaox/p/11294278.html