递归函数推导
994 / 0 / 创建于 5年前 /
jcc123 的个人博客
遞歸函數推導
重要的事情説三遍！！！
- 遞歸是循環的語法糖,是順序執行的
- 遞歸是循環的語法糖,是順序執行的
- 遞歸是循環的語法糖,是順序執行的
假設你要的到這樣的一個數組
$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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：