Artikel ini akan memperkenalkan anda kepada rekursi dan memperkenalkan pengoptimuman rekursi dalam PHP 7.
Rekursi sering digunakan dalam pengaturcaraan kerana kesederhanaan dan keanggunannya. Kod rekursif lebih bersifat deklaratif dan menggambarkan diri. Rekursi tidak perlu menerangkan cara mendapatkan nilai seperti lelaran, sebaliknya menerangkan hasil akhir fungsi.
Ambil pelaksanaan akumulasi dan jujukan Fibonacci sebagai contoh:
// 累加函数
// 给定参数 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);
} Sebagai perbandingan, pelaksanaan rekursif adalah lebih ringkas dan jelas, lebih mudah dibaca dan lebih mudah difahami.
Panggilan fungsi dalam program biasanya perlu mengikut konvensyen panggilan tertentu di peringkat bawah. Proses biasa ialah:
Proses ini sangat pantas dalam bahasa peringkat rendah (seperti sebagai pemasangan), kerana bahasa peringkat rendah berinteraksi secara langsung dengan CPU, dan operasi CPU Sangat pantas. Dalam Linux dengan seni bina x86_64, parameter sering dihantar terus melalui daftar, dan ruang tindanan dalam memori akan dimuatkan ke dalam cache CPU, supaya CPU boleh mengakses ruang tindanan dengan sangat cepat.
Proses yang sama adalah berbeza sama sekali dalam bahasa peringkat tinggi seperti PHP. Bahasa peringkat tinggi tidak boleh berinteraksi secara langsung dengan CPU dan perlu menggunakan mesin maya untuk memayakan set konsep seperti timbunan dan timbunan. Pada masa yang sama, mesin maya juga diperlukan untuk mengekalkan dan mengurus timbunan maya ini.
Proses panggilan fungsi dalam bahasa peringkat tinggi sudah sangat perlahan berbanding bahasa peringkat rendah, dan pengulangan akan memburukkan keadaan ini. Mengambil fungsi pengumpulan dalam contoh di atas sebagai contoh, ZVM perlu membina timbunan panggilan fungsi untuk setiap sumBelow (pembinaan khusus timbunan panggilan telah dibincangkan dalam artikel sebelumnya Apabila n meningkat, timbunan panggilan perlu akan dibina Akan semakin banyak, akhirnya membawa kepada limpahan ingatan. Berbanding dengan fungsi terkumpul, pengulangan fungsi Fibonacci akan meningkatkan bilangan tindanan panggilan dalam janjang geometri (kerana setiap tindanan panggilan akhirnya akan menghasilkan dua tindanan panggilan baharu).
Panggilan ekor merujuk kepada a fungsi yang hanya mengembalikan panggilan kepada dirinya sendiri pada akhirnya, tanpa sebarang operasi lain. Kerana fungsi mengembalikan panggilan kepada dirinya sendiri, pengkompil boleh menggunakan semula tindanan panggilan semasa tanpa membuat tindanan panggilan baharu.
Tukar fungsi pengumpulan dan fungsi Fibonacci yang dinyatakan di atas kepada pelaksanaan panggilan ekor, kodnya adalah seperti berikut
// 累加函数的尾调用方式实现
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);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// 主函数
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 dalam kelas adalah tail-called ialah sum , pelaksanaan asas yang sepadan ialah: 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视频教程》
Atas ialah kandungan terperinci Lihat cara untuk mengoptimumkan rekursi dalam PHP 7!. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Bagaimana untuk memuat turun video dari Douyin
Apakah kekunci pintasan untuk saiz berus?
Pengenalan kepada komponen laravel
Bagaimana untuk menyambung php ke pangkalan data mssql
Pengenalan kepada kekunci pintasan untuk meminimumkan tingkap tingkap
Bagaimana untuk membina pangkalan data dalam MySQL
penggunaan sisipan oracle
Bagaimana untuk membuka akaun dengan mata wang u
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
