本篇文章带大家了解一下递归，介绍一下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];}
递归方式实现// 累加函数function sumbelow(int $n) { if ($n <= 1) { return 1; } return $n + sumbelow($n - 1);}// 斐波那契数列function fib(int $n) { if ($n < 2) { return 1; } return fib($n - 1) + fib($n - 2);}
相比之下，递归的实现方式更简洁明了，可读性更强，更容易理解。
⒉ 递归存在的问题  程序中的函数调用，在底层通常需要遵循一定的调用约定（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 1l2: v3 = fetch_dim_func_arg cv1($argv) int(1)l3: send_func_arg v3 1l4: do_fcalll5: assign cv0($t) v2l6: init_fcall 1 96 string("memory_get_peak_usage")l7: send_val bool(true) 1l8: v6 = do_icalll9: echo v6l10: echo string("")l11: return int(1)// 构造函数l0: cv0($n) = recv 1l1: init_method_call 1 this string("sum")l2: send_var_ex cv0($n) 1l3: do_fcalll4: return null// 累加函数l0: cv0($n) = recv 1l1: cv1($sum) = recv_init 2 int(1)l2: t2 = is_smaller_or_equal cv0($n) int(1)l3: jmpz t2 l5l4: return cv1($sum)l5: init_method_call 2 this string("sum")l6: t3 = sub cv0($n) int(1)l7: send_val_ex t3 1l8: t4 = add cv1($sum) cv0($n)l9: send_val_ex t4 2l10: v5 = do_fcalll11: return v5l12: 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中怎么优化递归的！的详细内容。