但行好事,莫问前程

挖了太多坑,一点点填回来

递归与迭代

php, 文艺女与理工男

虽然题目写的是《递归与迭代》这么一个 geek 的标题,不过接下来的故事我其实是想写一个文艺女与理工男的故事。

写这篇文章的动机来自 http://weibo.com/1649186337/AmLoK2Upy 。未来的社会,会写代码的人越来越多,编程就像今天的外语技能一样,会成为一项基本技能。

OK,先来设定一下故事背景:文艺女与理工男目前处在暧昧期,目前还没有确立关系,不过经常混在一起,理工男给文艺女普及一些电脑知识,文艺女教会理工男享受生活。

这一天,理工男又给文艺女上编程课了,当然教她的语言是世界上最好的语言——PHP,文艺女已经了解了这门语言的基本语法,今天理工男就要教她递归

男:好,今天我们来学习递归。你知道递归是什么吗?

女:不知道,那我先去 Google 一下~咦,怎么会是这个样子?

递归

男:哈哈,果然让你碰到了这个坑。其实递归是指在函数的定义中使用函数自身的方法。高中的时候学过 fibonacci 数列吧?

女:嗯,这个我知道。f(x) = f(x-1) + f(x-2),其中 f(1) = 1,f(2) = 1。

男:很好,你从这个公式里就可以看到函数调用了自身,之前你已经学过了函数如何定义和调用,下面来试着自己写一下代码吧?

女:好,我来试试。你看下面这个行不行?

使用递归的 fibonacci 数列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?php
/**
 * 使用递归的 fibonacci 数列
 *
 * @param $n
 * @return bool|int
 */
function fibonacci($n) {
    if ($n < 0) {
        return false;
    }
    if ($n === 0) {
        return 0;
    } elseif ($n === 1) {
        return 1;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}

echo fibonacci(10);

男:哇,一下子就写对了,你是我见过最有编程天赋的女孩子,不如改行当程序员吧!你可以做 PHP 女神!

女:哼,本姑娘冰雪聪明,这点小意思难不倒我。

男:哦,那好吧,那你算一下 fibonacci 数列第 1000 个数字是多少?

女:换个参数就行了,看我的~咦,怎么结果是这样?

栈溢出了
1
Fatal error: Maximum function nesting level of '100' reached, aborting!

男:这牵涉到计算机系统中的概念和编程语言中使用来保存递归状态。你这个情况就是碰到栈溢出了。

女:栈是什么?溢出又是什么意思?

男:打个比方吧。你有一个瓶子和一堆小球,用来给递归的层数做一个计数器,每当递归的层数深入一层的时候,你就往瓶子里放一颗小球,直到把瓶子放满了……

女:瓶子放满了,后面的小球就再也放不进去了,递归层数就没办法继续做计数了,所以计算机就报错了,对不对?

男:Bingo!你真是太聪明了,一点就通啊,真的不考虑听我的建议转行当程序员?

女:哼,才不要~原来递归就好像《盗梦空间》里的多层梦境,栈的溢出就好比进入了 limbo 层,诺兰导演原来是个程序员!

男:你的这个解释很有新意……

女:那有没有别的办法求出第 1000 项的数字呢?

男:可以的,用迭代来代替递归即可。我之前教过你循环语句,你要不要试着改写一下代码,用循环来做?

女:好,那我试试。

使用迭代的 fibonacci 数列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php
/**
 * 使用迭代的 fibonacci 数列
 *
 * @param $n
 * @return bool|int
 */
function fibonacci_with_iteration($n) {
    if ($n < 0) {
        return false;
    }
    $fibo = array(0, 1);
    for ($i = 2; $i <= $n; ++$i) {
        $fibo[$i] = $fibo[$i - 1] + $fibo[$i - 2];
    }
    return $fibo[$n];
}

echo fibonacci_with_iteration(1000);

男:一点就通,果然很棒,不过你这个解法会造成大量内存空间的浪费,我重写一个版本给你吧。

节省内存空间的做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<?php
/**
 * 节省内存空间的做法
 *
 * @param $n
 * @return bool|int
 */
function fibonacci($n) {
    list($f0, $f1, $result) = array(0, 1, 1);
    if ($n < 0) {
        return false;
    }
    if ($n < 2) {
        return 1;
    }
    for ($i = 2; $i <= $n; ++$i) {
        $result = $f0 + $f1;
        $f0 = $f1;
        $f1 = $result;
    }
    return $result;
}

echo fibonacci(1000);

女:迭代这里看不懂啊……

男:呵呵,看不懂那我下次解释给你听,下回我再教你用面向对象的方式重写 fibonacci 数列的解决方案。

女:对象?你这么一个呆头呆脑的理工男还想有对象?

男:人艰不拆……

以上内容,纯属瞎掰,如有雷同,不胜荣幸。

Have a nice day!