递归函数推导
遞歸函數推導
重要的事情説三遍!!!
- 遞歸是循環的語法糖,是順序執行的
- 遞歸是循環的語法糖,是順序執行的
- 遞歸是循環的語法糖,是順序執行的
假設你要的到這樣的一個數組
$re = [1,2,3];
用循環的話,只需這樣
for($i=1;$i<=3;$i++){
$re[]=$i;
}
//$re = [1,2,3];
既然遞歸是循環的另一種寫法,那用遞歸怎么處理?
在這裏利用類似數學的歸納法,推出最終的遞歸函數。
首先定義一個函數,這個函數根據傳入參數返回不同的值.
例如
f(1)=[1]
f(2)=[2]
f(3)=[3]
則
$re = array_merge(f(1),f(2),f(3));
這個函數可以定義爲
function digui($i){
$arr = [$i];
return $arr;
}
對於這個函數,假如我調用
digui(3)
我希望返回數組
[1,2,3]
則這個函數需要個條件去判定終止,如下
function digui($i){
$arr = [$i];
if($i>1){
//todo
}
return $arr;
}
現在我調用 digui(3)
(先不考虑if)則 返回$arr=[3]
,現在[3]
有了,需要獲得到$arr=[2]
,在判定條件中加入
function digui($i){
$arr = [$i];
if($i>1){
$i--;
$digui= function ($i){
$arr = [$i];
if($i>1){
//todo
}
return $arr;
}
$digui($i);
}
return $arr;
}
可知$digui($i)
的值為[2]
,差個最後的[1]
。對於這個部分
$digui= function ($i){
$arr = [$i];
if($i>1){
//todo
}
return $arr;
}
$digui($i);
可以寫成這樣,方便理解
(function ($i){
$arr = [$i];
if($i>1){
//todo
}
return $arr;
})($i)
上面這個值返需要個變量接收,暫且定為$arr2
。最後去獲取[1]
的值
function digui($i){
$arr = [$i];
if($i>1){
$i--;
$arr2=(function ($i){
$arr = [$i];
if($i>1){
$i--;
$arr3=(function ($i){
$arr = [$i];
if($i>1){
//todo 這裏不進入了
}
return $arr;
})($i)
}
return $arr;
})($i)
}
return $arr;
}
可知 $arr=[3]
$arr2=[2]
$arr3=[1]
要獲得
[1,2,3]
只需 把最後一行改爲
return array_merge($arr3,$arr2,$arr);
即
function digui($i){
$arr = [$i];
if($i>1){
$i--;
$arr2=(function ($i){
$arr = [$i];
if($i>1){
$i--;
$arr3=(function ($i){
$arr = [$i];
if($i>1){
//todo 這裏不進入了
}
return $arr;
})($i);
}
return $arr;
})($i);
}
return array_merge($arr3,$arr2,$arr);
}
你會發現$arr3
這個參數在匿名函數内部,外部獲得不到。因此希望$arr2
的值為[1,2]
,然後在array_merge($arr2.$arr)
即可
function digui($i){
$arr = [$i];
if($i>1){
$i--;
$arr2=(function ($i){
$arr = [$i];
if($i>1){
$i--;
$arr3=(function ($i){
$arr = [$i];
$i--
if($i>1){
//todo 這裏不進入了
}
return $arr;
})($i);
}
return array_merge($arr3,$arr);
})($i);
}
return array_merge($arr2,$arr);
}
你可能發現上面的這個函數的公共部分為
$arr = [$i];
$i--
if($i>1){
//todo
}
但又不是那麽相似,最後的返回值不是那麽相同。從内到外依次是
return $arr;
return array_merge($arr3,$arr);
return array_merge($arr2,$arr);
因此只要把最後的返回值給構造出相同的結構,就可以推出遞歸函數了。
你可能發現 return $arr
可以寫為 return array_merge([],$arr)
因此上面的也可寫爲
return array_merge([],$arr);
return array_merge($arr3,$arr);
return array_merge($arr2,$arr);
因爲$arr3``$arr2
不可能[]
,所以需要定義一個變量這樣 $re=[]
function digui($i){
$arr = [$i];
if($i>1){
$i--;
$arr2=(function ($i){
$arr = [$i];
if($i>1){
$i--;
$arr3=(function ($i){
$arr = [$i];
$i--;
$re = [];//定義的變量
if($i>1){
//todo 這裏不進入了
}
return array_merge($re,$arr);
})($i);
}
return array_merge($arr3,$arr);
})($i);
}
return array_merge($arr2,$arr);
}
既然結構是相同的,那麽每一層都需要定義$re=[]
於是
function digui($i){
$arr = [$i];
$re = [];//保持和最内層結構相似
if($i>1){
$i--;
$arr2=(function ($i){
$arr = [$i];
$re = [];//保持和最内層結構相似
if($i>1){
$i--;
$arr3=(function ($i){
$arr = [$i];
$re = [];//定義的變量
if($i>1){
$i--;
//todo 這裏不進入了
}
return array_merge($re,$arr);
})($i);
}
return array_merge($arr3,$arr);
})($i);
}
return array_merge($arr2,$arr);
}
現在每一層都有一個變量$re
,你會發現其實$arr3
$arr2
其實也是定義的一個變量。既然現在每一層都有一個$re
變量,那麽就沒有必要用$arr3
,$arr2
替換爲$re
即
function digui($i){
$arr = [$i];
$re = [];//保持和最内層結構相似
if($i>1){
$i--;
$re=(function ($i){
$arr = [$i];
$re = [];//保持和最内層結構相似
if($i>1){
$i--;
$re=(function ($i){
$arr = [$i];
$re = [];//定義的變量
if($i>1){
$i--;
//todo 這裏不進入了
}
return array_merge($re,$arr);
})($i);
}
//return array_merge($arr3,$arr);
return array_merge($re,$arr);
})($i);
}
//return array_merge($arr2,$arr);
return array_merge($re,$arr);
}
現在每一層的返回值都爲
return array_merge($re,$arr);
相同的部分爲
$arr = [$i];
$re = [];
if($i>1){
$i--;
$re = xxx;
}
return array_merge($re,$arr);
只需把$re=xxx
的xxx
替換為'自己'即digui($i)
即
function digui($i){
$arr = [$i];
$re =[];
if($i>1){
$i--;
$re= digui($i);
}
return array_merge($re,$arr);
}
完
本作品采用《CC 协议》,转载必须注明作者和本文链接