本篇文章帶大家了解一下遞歸，介紹一下PHP 7 中對遞歸的最佳化。
⒈ 遞迴
遞歸因其簡潔、優雅的特性在程式設計中經常會被使用。遞歸的程式碼更具聲明性和自我描述性。遞歸不需要像迭代那樣解釋如何取得值，而是在描述函數的最終結果。
以累加與斐波那契數列的實作為例：
- 迭代方式實作
##// 累加函数
// 给定参数 n，求小于等于 n 的正整数的和
function sumBelow(int $n)
{
if ($n <= 0) {
return 0;
}
$result = 0;
for ($i = 1; $i <= $n; $i ++) {
$result += $i;
}
return $result;
}
// 斐波那契数列
// 给定参数 n，取得斐波那契数列中第 n 项的值
// 这里用数组模拟斐波那契数列，斐波那契数列第一项为 1，第二项为 2，初始化数组 $arr = [1, 1]，则斐波那契数列第 n 项的值为 $arr[n] = $arr[n-1] + $arr[n-2]
function fib(int $n)
{
if ($n <= 0) {
return false;
}
if ($n == 1) {
return 1;
}
$arr = [1, 1];
for ($i = 2, $i <= $n; $i ++) {
$arr[$i] = $arr[$i - 1] + $arr[$i - 2];
}
return $arr[$n];
}登入後複製
相較之下，遞迴的實作方式更簡潔明了，可讀性更強，也更容易理解。
⒉ 遞歸存在的問題
程式中的函數調用，在底層通常需要遵循一定的呼叫約定（calling convention）。通常的過程是：
首先將函數的參數和傳回位址入堆疊然後CPU 開始執行函數體中的程式碼最後在函數執行完成之後銷毀這塊佔空間，CPU 回到返回地址所指的位置
這個過程在低階語言（例如彙編）中非常快，因為低階語言直接與CPU 交互，而CPU 的運行速度非常快。在 x86_64 架構的 Linux 中，參數往往直接透過暫存器傳遞，記憶體中的堆疊空間會預先載入到 CPU 的快取中，這樣 CPU 反問棧空間就會非常非常快。
同樣的過程在高階語言（例如 PHP）中卻截然不同。高階語言無法直接與 CPU 交互，需要藉助虛擬機器來虛擬化一套自身的堆疊、堆疊等概念。同時，也需要藉助虛擬機器來維護和管理這套虛擬化出來的堆疊。
高階語言中的函式呼叫過程相較於低階語言已經很慢，而遞迴會讓這種情況雪上加霜。以上例中的累加函數為例，每到一個
sumBelow，ZVM 都需要建構一個函數呼叫堆疊（具體呼叫堆疊的構造之前的文章已經講過），隨著n 的增大，需要構造的呼叫棧會越來越多，最終導致記憶體溢位。相較於累加函數，斐波那契函數的遞歸會使得呼叫堆疊的數量呈現幾何級數式的增加（因為每一個呼叫堆疊最終會新產生兩個呼叫堆疊）。
⒊ 使用彈翻床函數（trampoline）和尾呼叫（tail call）來最佳化遞迴
① 尾呼叫
尾調用指的是一個函數最後只返回對自身的調用，再沒有其他的任何操作。由於函數返回的是對自身的調用，因此編譯器可以復用當前的調用堆疊而不需要新建調用棧。
將前述的累加函數與斐波那契函數改為尾呼叫的實作方式，程式碼如下
// 累加函数的尾调用方式实现
function subBelow(int $n, int $sum = 1)
{
if ($n <= 1) {
return $sum;
}
return subBelow($n - 1, $sum + $n);
}
// 斐波那契函数的尾调用实现
function fib(int $n, int $acc1 = 1, int $acc2 = 2)
{
if ($n < 2) {
return $acc1;
}
return fib($n - 1, $acc1 + $acc2, $acc1);
}登入後複製
② 彈翻床函數
累加函數相對簡單，可以很方便的轉換成尾呼叫的實作方式。斐波那契函數的尾呼叫實作方式就相對比較麻煩。但在實際應用中，許多遞歸夾雜著許多複雜的條件判斷，在不同的條件下進行不同方式的遞迴。此時，無法直接把遞歸函數轉換成尾呼叫的形式，需要藉助蹦床函數。
所謂彈翻床函數，其基本原理是將遞歸函數包裝成迭代的形式。以累加函數為例，首先改寫累加函數的實作方式：
function trampolineSumBelow(int $n, int $sum = 1)
{
if ($n <= 1) {
return $sum;
}
return function() use ($n, $sum) { return trampolineSumBelow($n - 1, $sum + $n); };
}登入後複製
在函數的最後並沒有直接進行遞歸調用，而是把遞歸調用包裝進了一個閉包，而閉包函數不會立即執行。此時需要藉助蹦床函數，如果彈翻床函數發現回傳的是一個閉包，那麼彈翻床函數會繼續執行回傳的閉包，知道彈翻床函數發現回傳的是一個值。
function trampoline(callable $cloure, ...$args)
{
while (is_callable($cloure)) {
$cloure = $cloure(...$args);
}
return $cloure;
}
echo trampoline('trampolineSumBelow', 100);登入後複製
彈翻床函數是一種比較通用的解決遞歸呼叫的問題的方式。在彈翻床函數中，傳回的閉包被以迭代的方式執行，避免了函數遞歸導致的記憶體溢位。
⒋ ZVM 中對遞歸的最佳化
在 PHP 7 中，透過尾呼叫的方式最佳化遞迴主要應用在物件的方法中。仍以累加函數為例：
class Test
{
public function __construct(int $n)
{
$this->sum($n);
}
public function sum(int $n, int $sum = 1)
{
if ($n <= 1) {
return $sum;
}
return $this->sum($n - 1, $sum + $n);
}
}
$t = new Test($argv[1]);
echo memory_get_peak_usage(true), PHP_EOL;
// 经测试，在 $n <= 10000 的条件下，内存消耗的峰值恒定为 2M登入後複製
以上程式碼對應的OPCode 為：
// 主函数
L0: V2 = NEW 1 string("Test")
L1: CHECK_FUNC_ARG 1
L2: V3 = FETCH_DIM_FUNC_ARG CV1($argv) int(1)
L3: SEND_FUNC_ARG V3 1
L4: DO_FCALL
L5: ASSIGN CV0($t) V2
L6: INIT_FCALL 1 96 string("memory_get_peak_usage")
L7: SEND_VAL bool(true) 1
L8: V6 = DO_ICALL
L9: ECHO V6
L10: ECHO string("
")
L11: RETURN int(1)
// 构造函数
L0: CV0($n) = RECV 1
L1: INIT_METHOD_CALL 1 THIS string("sum")
L2: SEND_VAR_EX CV0($n) 1
L3: DO_FCALL
L4: RETURN null
// 累加函数
L0: CV0($n) = RECV 1
L1: CV1($sum) = RECV_INIT 2 int(1)
L2: T2 = IS_SMALLER_OR_EQUAL CV0($n) int(1)
L3: JMPZ T2 L5
L4: RETURN CV1($sum)
L5: INIT_METHOD_CALL 2 THIS string("sum")
L6: T3 = SUB CV0($n) int(1)
L7: SEND_VAL_EX T3 1
L8: T4 = ADD CV1($sum) CV0($n)
L9: SEND_VAL_EX T4 2
L10: V5 = DO_FCALL
L11: RETURN V5
L12: RETURN null登入後複製
當class 中的累加函數
sum 發生尾呼叫時執行的OPCode 為DO_FCALL ，對應的底層實作為：
# define ZEND_VM_CONTINUE() return
# define LOAD_OPLINE() opline = EX(opline)
# define ZEND_VM_ENTER() execute_data = EG(current_execute_data); LOAD_OPLINE(); ZEND_VM_INTERRUPT_CHECK(); ZEND_VM_CONTINUE()
static ZEND_OPCODE_HANDLER_RET ZEND_FASTCALL ZEND_DO_FCALL_SPEC_RETVAL_USED_HANDLER(ZEND_OPCODE_HANDLER_ARGS)
{
USE_OPLINE
zend_execute_data *call = EX(call);
zend_function *fbc = call->func;
zend_object *object;
zval *ret;
SAVE_OPLINE();
EX(call) = call->prev_execute_data;
/* 判断所调用的方法是否为抽象方法或已废弃的函数 */
/* ... ... */
LOAD_OPLINE();
if (EXPECTED(fbc->type == ZEND_USER_FUNCTION)) {
/* 所调用的方法为开发者自定义的方法 */
ret = NULL;
if (1) {
ret = EX_VAR(opline->result.var);
ZVAL_NULL(ret);
}
call->prev_execute_data = execute_data;
i_init_func_execute_data(call, &fbc->op_array, ret);
if (EXPECTED(zend_execute_ex == execute_ex)) {
/* zend_execute_ex == execute_ex 说明方法调用的是自身，发生递归*/
ZEND_VM_ENTER();
} else {
ZEND_ADD_CALL_FLAG(call, ZEND_CALL_TOP);
zend_execute_ex(call);
}
} else if (EXPECTED(fbc->type < ZEND_USER_FUNCTION)) {
/* 内部方法调用 */
/* ... ... */
} else { /* ZEND_OVERLOADED_FUNCTION */
/* 重载的方法 */
/* ... ... */
}
fcall_end:
/* 异常判断以及相应的后续处理 */
/* ... ... */
zend_vm_stack_free_call_frame(call);
/* 异常判断以及相应的后续处理 */
/* ... ... */
ZEND_VM_SET_OPCODE(opline + 1);
ZEND_VM_CONTINUE();
}登入後複製
从 DO_FCALL 的底层实现可以看出，当发生方法递归调用时（zend_execute_ex == execute_ex），ZEND_VM_ENTER() 宏将 execute_data 转换为当前方法的 execute_data ，同时将 opline 又置为 execute_data 中的第一条指令，在检查完异常（ZEND_VM_INTERRUPT_CHECK()）之后，返回然后重新执行方法。
通过蹦床函数的方式优化递归调用主要应用在对象的魔术方法 __call 、__callStatic 中。
class A
{
private function test($n)
{
echo "test $n", PHP_EOL;
}
public function __call($method, $args)
{
$this->$method(...$args);
var_export($this);
echo PHP_EOL;
}
}
class B extends A
{
public function __call($method, $args)
{
(new parent)->$method(...$args);
var_export($this);
echo PHP_EOL;
}
}
class C extends B
{
public function __call($method, $args)
{
(new parent)->$method(...$args);
var_export($this);
echo PHP_EOL;
}
}
$c = new C();
//$c->test(11);
echo memory_get_peak_usage(), PHP_EOL;
// 经测试，仅初始化 $c 对象消耗的内存峰值为 402416 字节，调用 test 方法所消耗的内存峰值为 431536 字节登入後複製
在对象中尝试调用某个方法时，如果该方法在当前对象中不存在或访问受限（protected、private），则会调用对象的魔术方法 __call（如果通过静态调用的方式，则会调用 __callStatic）。在 PHP 的底层实现中，该过程通过 zend_std_get_method 函数实现
static union _zend_function *zend_std_get_method(zend_object **obj_ptr, zend_string *method_name, const zval *key)
{
zend_object *zobj = *obj_ptr;
zval *func;
zend_function *fbc;
zend_string *lc_method_name;
zend_class_entry *scope = NULL;
ALLOCA_FLAG(use_heap);
if (EXPECTED(key != NULL)) {
lc_method_name = Z_STR_P(key);
#ifdef ZEND_ALLOCA_MAX_SIZE
use_heap = 0;
#endif
} else {
ZSTR_ALLOCA_ALLOC(lc_method_name, ZSTR_LEN(method_name), use_heap);
zend_str_tolower_copy(ZSTR_VAL(lc_method_name), ZSTR_VAL(method_name), ZSTR_LEN(method_name));
}
/* 所调用的方法在当前对象中不存在 */
if (UNEXPECTED((func = zend_hash_find(&zobj->ce->function_table, lc_method_name)) == NULL)) {
if (UNEXPECTED(!key)) {
ZSTR_ALLOCA_FREE(lc_method_name, use_heap);
}
if (zobj->ce->__call) {
/* 当前对象存在魔术方法 __call */
return zend_get_user_call_function(zobj->ce, method_name);
} else {
return NULL;
}
}
/* 所调用的方法为 protected 或 private 类型时的处理逻辑 */
/* ... ... */
}
static zend_always_inline zend_function *zend_get_user_call_function(zend_class_entry *ce, zend_string *method_name)
{
return zend_get_call_trampoline_func(ce, method_name, 0);
}
ZEND_API zend_function *zend_get_call_trampoline_func(zend_class_entry *ce, zend_string *method_name, int is_static)
{
size_t mname_len;
zend_op_array *func;
zend_function *fbc = is_static ? ce->__callstatic : ce->__call;
ZEND_ASSERT(fbc);
if (EXPECTED(EG(trampoline).common.function_name == NULL)) {
func = &EG(trampoline).op_array;
} else {
func = ecalloc(1, sizeof(zend_op_array));
}
func->type = ZEND_USER_FUNCTION;
func->arg_flags[0] = 0;
func->arg_flags[1] = 0;
func->arg_flags[2] = 0;
func->fn_flags = ZEND_ACC_CALL_VIA_TRAMPOLINE | ZEND_ACC_PUBLIC;
if (is_static) {
func->fn_flags |= ZEND_ACC_STATIC;
}
func->opcodes = &EG(call_trampoline_op);
func->prototype = fbc;
func->scope = fbc->common.scope;
/* reserve space for arguments, local and temorary variables */
func->T = (fbc->type == ZEND_USER_FUNCTION)? MAX(fbc->op_array.last_var + fbc->op_array.T, 2) : 2;
func->filename = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.filename : ZSTR_EMPTY_ALLOC();
func->line_start = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.line_start : 0;
func->line_end = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.line_end : 0;
//??? keep compatibility for "\0" characters
//??? see: Zend/tests/bug46238.phpt
if (UNEXPECTED((mname_len = strlen(ZSTR_VAL(method_name))) != ZSTR_LEN(method_name))) {
func->function_name = zend_string_init(ZSTR_VAL(method_name), mname_len, 0);
} else {
func->function_name = zend_string_copy(method_name);
}
return (zend_function*)func;
}
static void zend_init_call_trampoline_op(void)
{
memset(&EG(call_trampoline_op), 0, sizeof(EG(call_trampoline_op)));
EG(call_trampoline_op).opcode = ZEND_CALL_TRAMPOLINE;
EG(call_trampoline_op).op1_type = IS_UNUSED;
EG(call_trampoline_op).op2_type = IS_UNUSED;
EG(call_trampoline_op).result_type = IS_UNUSED;
ZEND_VM_SET_OPCODE_HANDLER(&EG(call_trampoline_op));
}登入後複製
ZEND_CALL_TRAMPOLINE 的底层实现逻辑：
static ZEND_OPCODE_HANDLER_RET ZEND_FASTCALL ZEND_CALL_TRAMPOLINE_SPEC_HANDLER(ZEND_OPCODE_HANDLER_ARGS)
{
zend_array *args;
zend_function *fbc = EX(func);
zval *ret = EX(return_value);
uint32_t call_info = EX_CALL_INFO() & (ZEND_CALL_NESTED | ZEND_CALL_TOP | ZEND_CALL_RELEASE_THIS);
uint32_t num_args = EX_NUM_ARGS();
zend_execute_data *call;
USE_OPLINE
args = emalloc(sizeof(zend_array));
zend_hash_init(args, num_args, NULL, ZVAL_PTR_DTOR, 0);
if (num_args) {
zval *p = ZEND_CALL_ARG(execute_data, 1);
zval *end = p + num_args;
zend_hash_real_init(args, 1);
ZEND_HASH_FILL_PACKED(args) {
do {
ZEND_HASH_FILL_ADD(p);
p++;
} while (p != end);
} ZEND_HASH_FILL_END();
}
SAVE_OPLINE();
call = execute_data;
execute_data = EG(current_execute_data) = EX(prev_execute_data);
ZEND_ASSERT(zend_vm_calc_used_stack(2, fbc->common.prototype) <= (size_t)(((char*)EG(vm_stack_end)) - (char*)call));
call->func = fbc->common.prototype;
ZEND_CALL_NUM_ARGS(call) = 2;
ZVAL_STR(ZEND_CALL_ARG(call, 1), fbc->common.function_name);
ZVAL_ARR(ZEND_CALL_ARG(call, 2), args);
zend_free_trampoline(fbc);
fbc = call->func;
if (EXPECTED(fbc->type == ZEND_USER_FUNCTION)) {
if (UNEXPECTED(!fbc->op_array.run_time_cache)) {
init_func_run_time_cache(&fbc->op_array);
}
i_init_func_execute_data(call, &fbc->op_array, ret);
if (EXPECTED(zend_execute_ex == execute_ex)) {
ZEND_VM_ENTER();
} else {
ZEND_ADD_CALL_FLAG(call, ZEND_CALL_TOP);
zend_execute_ex(call);
}
} else {
/* ... ... */
}
/* ... ... */
}登入後複製
从 ZEND_CALL_TRAMPOLINE 的底层实现可以看出，当发生 __call 的递归调用时（上例中 class C、class B、class A 中依次发生 __call 的调用），ZEND_VM_ENTER 将 execute_data 和 opline 进行变换，然后重新执行。
递归之后还需要返回，返回的功能在 RETURN 中实现。所有的 PHP 代码在编译成 OPCode 之后，最后一条 OPCode 指令一定是 RETURN（即使代码中没有 return，编译时也会自动添加）。而在 ZEND_RETURN 中，最后一步要执行的操作为 zend_leave_helper ，递归的返回即时在这一步完成。
# define LOAD_NEXT_OPLINE() opline = EX(opline) + 1
# define ZEND_VM_CONTINUE() return
# define ZEND_VM_LEAVE() ZEND_VM_CONTINUE()
static ZEND_OPCODE_HANDLER_RET ZEND_FASTCALL zend_leave_helper_SPEC(ZEND_OPCODE_HANDLER_ARGS)
{
zend_execute_data *old_execute_data;
uint32_t call_info = EX_CALL_INFO();
if (EXPECTED((call_info & (ZEND_CALL_CODE|ZEND_CALL_TOP|ZEND_CALL_HAS_SYMBOL_TABLE|ZEND_CALL_FREE_EXTRA_ARGS|ZEND_CALL_ALLOCATED)) == 0)) {
/* ... ... */
LOAD_NEXT_OPLINE();
ZEND_VM_LEAVE();
} else if (EXPECTED((call_info & (ZEND_CALL_CODE|ZEND_CALL_TOP)) == 0)) {
i_free_compiled_variables(execute_data);
if (UNEXPECTED(call_info & ZEND_CALL_HAS_SYMBOL_TABLE)) {
zend_clean_and_cache_symbol_table(EX(symbol_table));
}
EG(current_execute_data) = EX(prev_execute_data);
/* ... ... */
zend_vm_stack_free_extra_args_ex(call_info, execute_data);
old_execute_data = execute_data;
execute_data = EX(prev_execute_data);
zend_vm_stack_free_call_frame_ex(call_info, old_execute_data);
if (UNEXPECTED(EG(exception) != NULL)) {
const zend_op *old_opline = EX(opline);
zend_throw_exception_internal(NULL);
if (RETURN_VALUE_USED(old_opline)) {
zval_ptr_dtor(EX_VAR(old_opline->result.var));
}
HANDLE_EXCEPTION_LEAVE();
}
LOAD_NEXT_OPLINE();
ZEND_VM_LEAVE();
} else if (EXPECTED((call_info & ZEND_CALL_TOP) == 0)) {
/* ... ... */
LOAD_NEXT_OPLINE();
ZEND_VM_LEAVE();
} else {
/* ... ... */
}
}登入後複製
在 zend_leave_helper 中，execute_data 又被换成了 prev_execute_data ，然后继续执行新的 execute_data 的 opline（注意：这里并没有将 opline 初始化为 execute_data 中 opline 的第一条 OPCode，而是接着之前执行到的位置继续执行下一条 OPCode）。
推荐学习：《PHP视频教程》
以上是看看PHP 7怎麼優化遞歸的！的詳細內容。更多資訊請關注PHP中文網其他相關文章！
