本篇文章帶大家了解一下遞歸，介紹一下PHP 7 中對(duì)遞歸的優(yōu)化。

⒈ 遞歸

??遞歸因其簡(jiǎn)潔、優(yōu)雅的特性在編程中經(jīng)常會(huì)被使用。遞歸的代碼更具聲明性和自我描述性。遞歸不需要像迭代那樣解釋如何獲取值，而是在描述函數(shù)的最終結(jié)果。

??以累加和斐波那契數(shù)列的實(shí)現(xiàn)為例：

• 迭代方式實(shí)現(xiàn)

// 累加函數(shù) // 給定參數(shù) n，求小于等于 n 的正整數(shù)的和 function sumBelow(int $n) {     if ($n <= 0) {         return 0;     }     $result = 0;     for ($i = 1; $i <= $n; $i ++) {         $result += $i;     }     return $result; }  // 斐波那契數(shù)列 // 給定參數(shù) n，取得斐波那契數(shù)列中第 n 項(xiàng)的值 // 這里用數(shù)組模擬斐波那契數(shù)列，斐波那契數(shù)列第一項(xiàng)為 1，第二項(xiàng)為 2，初始化數(shù)組 $arr = [1, 1]，則斐波那契數(shù)列第 n 項(xiàng)的值為 $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]; }

• 遞歸方式實(shí)現(xiàn)

// 累加函數(shù) function sumBelow(int $n)  {     if ($n <= 1) {         return 1;     }     return $n + sumBelow($n - 1); }  // 斐波那契數(shù)列 function fib(int $n)  {     if ($n < 2) {         return 1;     }     return fib($n - 1) + fib($n - 2); }

??相比之下，遞歸的實(shí)現(xiàn)方式更簡(jiǎn)潔明了，可讀性更強(qiáng)，更容易理解。

⒉ 遞歸存在的問(wèn)題

??程序中的函數(shù)調(diào)用，在底層通常需要遵循一定的調(diào)用約定（calling convention）。通常的過(guò)程是：

• 首先將函數(shù)的參數(shù)和返回地址入棧
• 然后 CPU 開(kāi)始執(zhí)行函數(shù)體中的代碼
• 最后在函數(shù)執(zhí)行完成之后銷(xiāo)毀這塊占空間，CPU 回到返回地址所指的位置

??這個(gè)過(guò)程在低級(jí)語(yǔ)言（例如匯編）中非常快，因?yàn)榈图?jí)語(yǔ)言直接與 CPU 交互，而 CPU 的運(yùn)行速度非?？臁Ｔ?x86_64 架構(gòu)的 Linux 中，參數(shù)往往直接通過(guò)寄存器傳遞，內(nèi)存中的?？臻g會(huì)被預(yù)加載到 CPU 的緩存中，這樣 CPU 反問(wèn)棧空間會(huì)非常非?？?。

??同樣的過(guò)程在高級(jí)語(yǔ)言（例如 PHP）中卻截然不同。高級(jí)語(yǔ)言無(wú)法直接與 CPU 交互，需要借助虛擬機(jī)來(lái)虛擬化一套自身的堆、棧等概念。同時(shí)，還需要借助虛擬機(jī)來(lái)維護(hù)和管理這套虛擬化出來(lái)的堆棧。

??高級(jí)語(yǔ)言中的函數(shù)調(diào)用過(guò)程相較于低級(jí)語(yǔ)言已經(jīng)很慢，而遞歸會(huì)讓這種情況雪上加霜。以上例中的累加函數(shù)為例，每到一個(gè) sumBelow，ZVM 都需要構(gòu)造一個(gè)函數(shù)調(diào)用棧（具體調(diào)用棧的構(gòu)造之前的文章已經(jīng)講過(guò)），隨著 n 的增大，需要構(gòu)造的調(diào)用棧會(huì)越來(lái)越多，最終導(dǎo)致內(nèi)存溢出。相較于累加函數(shù)，斐波那契函數(shù)的遞歸會(huì)使得調(diào)用棧的數(shù)量呈現(xiàn)幾何級(jí)數(shù)式的增加（因?yàn)槊恳粋€(gè)調(diào)用棧最終會(huì)新產(chǎn)生兩個(gè)調(diào)用棧）。

⒊ 使用蹦床函數(shù)（trampoline）和尾調(diào)用（tail call）來(lái)優(yōu)化遞歸

??① 尾調(diào)用

??尾調(diào)用指的是一個(gè)函數(shù)最后只返回對(duì)自身的調(diào)用，再?zèng)]有其他的任何操作。由于函數(shù)返回的是對(duì)自身的調(diào)用，因此編譯器可以復(fù)用當(dāng)前的調(diào)用棧而不需要新建調(diào)用棧。

??將前述的累加函數(shù)和斐波那契函數(shù)改為尾調(diào)用的實(shí)現(xiàn)方式，代碼如下

// 累加函數(shù)的尾調(diào)用方式實(shí)現(xiàn) function subBelow(int $n, int $sum = 1) {     if ($n <= 1) {         return $sum;     }          return subBelow($n - 1, $sum + $n); }  // 斐波那契函數(shù)的尾調(diào)用實(shí)現(xiàn) function fib(int $n, int $acc1 = 1, int $acc2 = 2)  {     if ($n < 2) {         return $acc1;     }          return fib($n - 1, $acc1 + $acc2, $acc1); }

??② 蹦床函數(shù)

??累加函數(shù)相對(duì)簡(jiǎn)單，可以很方便的轉(zhuǎn)換成尾調(diào)用的實(shí)現(xiàn)方式。斐波那契函數(shù)的尾調(diào)用實(shí)現(xiàn)方式就相對(duì)比較麻煩。但在實(shí)際應(yīng)用中，很多遞歸夾雜著很多復(fù)雜的條件判斷，在不同的條件下進(jìn)行不同方式的遞歸。此時(shí)，無(wú)法直接把遞歸函數(shù)轉(zhuǎn)換成尾調(diào)用的形式，需要借助蹦床函數(shù)。

??所謂蹦床函數(shù)，其基本原理是將遞歸函數(shù)包裝成迭代的形式。以累加函數(shù)為例，首先改寫(xiě)累加函數(shù)的實(shí)現(xiàn)方式：

function trampolineSumBelow(int $n, int $sum = 1) {     if ($n <= 1) {         return $sum;     }          return function() use ($n, $sum) { return trampolineSumBelow($n - 1, $sum + $n); }; }

??在函數(shù)的最后并沒(méi)有直接進(jìn)行遞歸調(diào)用，而是把遞歸調(diào)用包裝進(jìn)了一個(gè)閉包，而閉包函數(shù)不會(huì)立即執(zhí)行。此時(shí)需要借助蹦床函數(shù)，如果蹦床函數(shù)發(fā)現(xiàn)返回的是一個(gè)閉包，那么蹦床函數(shù)會(huì)繼續(xù)執(zhí)行返回的閉包，知道蹦床函數(shù)發(fā)現(xiàn)返回的是一個(gè)值。

function trampoline(callable $cloure, ...$args) {     while (is_callable($cloure)) {         $cloure = $cloure(...$args);     }          return $cloure; }  echo trampoline('trampolineSumBelow', 100);

??蹦床函數(shù)是一種比較通用的解決遞歸調(diào)用的問(wèn)題的方式。在蹦床函數(shù)中，返回的閉包被以迭代的方式執(zhí)行，避免了函數(shù)遞歸導(dǎo)致的內(nèi)存溢出。

⒋ ZVM 中對(duì)遞歸的優(yōu)化

??在 PHP 7 中，通過(guò)尾調(diào)用的方式優(yōu)化遞歸主要應(yīng)用在對(duì)象的方法中。仍然以累加函數(shù)為例：

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;  // 經(jīng)測(cè)試，在 $n <= 10000 的條件下，內(nèi)存消耗的峰值恒定為 2M

??以上代碼對(duì)應(yīng)的 OPCode 為：

// 主函數(shù) 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)  // 構(gòu)造函數(shù) 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  // 累加函數(shù) 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

??當(dāng) class 中的累加函數(shù) sum 發(fā)生尾調(diào)用時(shí)執(zhí)行的 OPCode 為 DO_FCALL ，對(duì)應(yīng)的底層實(shí)現(xiàn)為：

# 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; 	/* 判斷所調(diào)用的方法是否為抽象方法或已廢棄的函數(shù) */ 	/* ... ... */  	LOAD_OPLINE();  	if (EXPECTED(fbc->type == ZEND_USER_FUNCTION)) { 		/* 所調(diào)用的方法為開(kāi)發(fā)者自定義的方法 */ 		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 說(shuō)明方法調(diào)用的是自身，發(fā)生遞歸*/ 			ZEND_VM_ENTER(); 		} else { 			ZEND_ADD_CALL_FLAG(call, ZEND_CALL_TOP); 			zend_execute_ex(call); 		} 	} else if (EXPECTED(fbc->type < ZEND_USER_FUNCTION)) { 		/* 內(nèi)部方法調(diào)用 */ 		/* ... ... */ 	} else { /* ZEND_OVERLOADED_FUNCTION */ 		/* 重載的方法 */ 		/* ... ... */ 	}  fcall_end: 	/* 異常判斷以及相應(yīng)的后續(xù)處理 */ 	/* ... ... */  	zend_vm_stack_free_call_frame(call); 	/* 異常判斷以及相應(yīng)的后續(xù)處理 */ 	/* ... ... */  	ZEND_VM_SET_OPCODE(opline + 1); 	ZEND_VM_CONTINUE(); }

??從 DO_FCALL 的底層實(shí)現(xiàn)可以看出，當(dāng)發(fā)生方法遞歸調(diào)用時(shí)（zend_execute_ex == execute_ex），ZEND_VM_ENTER() 宏將 execute_data 轉(zhuǎn)換為當(dāng)前方法的 execute_data ，同時(shí)將 opline 又置為 execute_data 中的第一條指令，在檢查完異常（ZEND_VM_INTERRUPT_CHECK()）之后，返回然后重新執(zhí)行方法。

??通過(guò)蹦床函數(shù)的方式優(yōu)化遞歸調(diào)用主要應(yīng)用在對(duì)象的魔術(shù)方法 __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;  // 經(jīng)測(cè)試，僅初始化 $c 對(duì)象消耗的內(nèi)存峰值為 402416 字節(jié)，調(diào)用 test 方法所消耗的內(nèi)存峰值為 431536 字節(jié)

??在對(duì)象中嘗試調(diào)用某個(gè)方法時(shí)，如果該方法在當(dāng)前對(duì)象中不存在或訪問(wèn)受限（protected、private），則會(huì)調(diào)用對(duì)象的魔術(shù)方法 __call（如果通過(guò)靜態(tài)調(diào)用的方式，則會(huì)調(diào)用 __callStatic）。在 PHP 的底層實(shí)現(xiàn)中，該過(guò)程通過(guò) zend_std_get_method 函數(shù)實(shí)現(xiàn)

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)); 	} 	 	/* 所調(diào)用的方法在當(dāng)前對(duì)象中不存在 */ 	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) { 			/* 當(dāng)前對(duì)象存在魔術(shù)方法 __call */ 			return zend_get_user_call_function(zobj->ce, method_name); 		} else { 			return NULL; 		} 	} 	/* 所調(diào)用的方法為 protected 或 private 類(lèi)型時(shí)的處理邏輯 */ 	/* ... ... */ }   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 "