PHP7中如何优化递归

这篇文章主要为大家展示了"PHP7中如何优化递归"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"PHP7中如何优化递归"这篇文章吧。

⒈ 递归

  递归因其简洁、优雅的特性在编程中经常会被使用。递归的代码更具声明性和自我描述性。递归不需要像迭代那样解释如何获取值，而是在描述函数的最终结果。

  以累加和斐波那契数列的实现为例：

• 迭代方式实现

// 累加函数// 给定参数 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）。

以上是"PHP7中如何优化递归"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！