钛节点

数据结构之栈和函数调用的二三事

发表@2018-09-13 09:15:22

更新@2023-01-21 22:47:40

写了一坨关于树的一些内容，其中对于树的某些操作，大量地运用了递归操作，那么，也是时候回来看一下递归了。

简单说来，一般我们通过“一个函数自己调用自己”来给递归下定义，其实这个还是比较难理解的：“妈蛋怎么能自己调用自己呢？你自己都还没定义完呢... ...什么玩意”。当然了，作为众多蠢货中的普通一员，即便我们不理解也没关系，死记硬背过又不是不行。

不过，作为PHP文化传播圣地，怎么能让你们白来一趟？同时我自己还能装一波儿13，两全其美、一石二鸟、一举两得。

有为青年看到标题后就已经在隐隐之间感受到了一些东西。本质上讲，递归就是“函数自己调用自己”，实际上这句话也就说递归就是一种函数调用而已。明人不装暗逼：函数调用利用的就是栈数据结构！没想到，作为CURDer混了这么多年，码了一坨函数调用来调用去，原来一直靠的是人家栈混饭吃。所以，掌握好数据结构什么的，那想必是... ...

“你记不记得有一招从天而降的掌法？”

![](https://ti-node.com/static/upload/6411222699867111425)

首先，我们从普通的函数调用开始，看下调用过程中栈究竟起到了什么作用，比如下面这坨代码：

```php
<?php
function a( $n ){
  echo "a func : ".$n.PHP_EOL;
  b( $n );
}
function b( $n ){
  echo "b func : ".$n.PHP_EOL;
  c( $n );
}
function c( $n ){
  echo "c func : ".$n.PHP_EOL;
}
a( 1 );
```

执行结果如下图所示：

![](https://ti-node.com/static/upload/6411225031006748673)

定义了三个函数a、b、c，其中a调用了b，b调用c，然后开始从函数a执行，画一个粗旷的流程图大概就是这个样子：a-》b-》c-》b-》a。有为青年可能已经搞明白为什么到了c之后还有b-》a，但是像我这样的蠢货可能会有点儿懵，难道不应该是到了c之后就再也没有然后了么？那么，我们把上述代码简单魔改一下：

```php
<?php
function a( $n ){
  echo "a func : ".$n.PHP_EOL;
  b( $n );
  echo "back to a func".PHP_EOL;
}
function b( $n ){
  echo "b func : ".$n.PHP_EOL;
  c( $n );
  echo "back to b func".PHP_EOL;
}
function c( $n ){
  echo "c func : ".$n.PHP_EOL;
}
a( 1 );
```

执行结果如下：

![](https://ti-node.com/static/upload/6411225511401357312)

运行印证了三个函数调用链就是从a-》b-》c-》b-》a，最终转了一圈又回到了a。其实，如果把上面代码写成下面这样，倒也一目了然，你们感受一下：

```php
<?php
function a( $n ){
  echo "a func : ".$n.PHP_EOL;  // a函数开始
    echo "b func : ".$n.PHP_EOL;  // b函数开始
      echo "c func : ".$n.PHP_EOL;  // c函数开始并结束
    echo "back to b func".PHP_EOL;  // b函数结束
  echo "back to a func".PHP_EOL;  // a函数结束
}
a( 1 );
```

然而，这种理解方式其实并不符合社会主义主流价值观，主流的社会主义价值体系是结合栈来理解上述代码。

当开始执行函数a的时候，将a的相关信息压入栈中；当在函数a中开始调用函数b的时候，将b的相关信息压入到栈中；当在函数b中调用函数c的时候，将c的相关信息压入到栈中；当函数c执行完毕后，将c的相关信息弹出栈，然后回到函数b中去；当函数b执行完毕后，将b的相关信息弹出栈，然后回到函数a中；当函数a执行完毕，将函数a相关信息弹出栈。整个过程，如下面所示：

![](https://ti-node.com/static/upload/6411228945957519360)

我们在这里值得记忆的一波儿有如下几个场景，第一是当a函数调用b函数的时候：

- 此时需要将实际参数和a函数的返回地址保存到b函数中
- 为b函数中变量等相关内容开辟内存存储区域
- 将程序控制权移交给b函数

当b函数执行完毕后，发生如下一些事情：

- 释放b函数所占据的内存空间
- 根据保存到b函数中的a函数返回地址再次回到a函数中继续往下执行
- 将程序控制权移交给a函数

话说到这里，其实已经比较直白了，实际上“a函数调用b函数”与“a函数调用a函数”是没有什么区别的，都是干了以上的事情，只不过用人类的语言一表达略微有点儿二逼而已。

话说回来，一般都会引入斐波那契数列来演示递归的日常用法，你们感受一下：

```php
<?php
function fibo( $n ){
  if( $n <= 0 ){
    throw new Exception('... ...');
  }
  if( 1 == $n ){
    return 1;  
  }else if( 2 == $n ){
    return 1;  
  }else{
    return fibo( $n - 1 ) + fibo( $n - 2 );  
  }
}
echo fibo( 3 ).PHP_EOL;
```

使用递归有些个值得注意的地方，最重要的一点就是递归一定要有终结条件，不然递归永远不会终止，也就是说就会永远向栈中压入新的元素，硬件资源是有限的，崩也是迟早的事情。比如上述斐波那契数列中，递归的终结条件就是当n<=2的时候。

有为青年实际上隐约之间还是能感受到一丝丝递归和循环的一些关系，实际上作为蠢货青年，当年我一度是分不清循环和递归的。实际上，二者相对比的话，重要区别有如下两点：

- 递归慢，循环快
- 递归占用空间大，循环占用空间小
- 我靠，递归这么辣鸡？也不是，递归相对来说比循环看起来更容易一些，而且，有些场合只能用递归来解决而循环无法解决，比如前几章中树的一些操作。用循环，那是不可能的，这辈子都不可能用循环的。

递归除了能解决斐波那契数列问题，在日常中，还解决了如下众多问题：

- 计算器。是的，计算器。你看到的计算器利用的就是递归。大家可以查看一下逆波兰等一些资料
- 求数的阶乘，你们可以尝试手写一些阶乘代码

```php
<?php
function jiecheng( $n ){
  if( $n <= 0 ){
    throw new Exception('... ...');
  }
  if( 1 == $n ){
    return 1;
  } else {
    return $n * jiecheng( $n - 1 );
  }
}
echo jiecheng( 3 ).PHP_EOL;
```