递归函数推导

遞歸函數推導

重要的事情説三遍！！！

• 遞歸是循環的語法糖,是順序執行的
• 遞歸是循環的語法糖,是順序執行的
• 遞歸是循環的語法糖,是順序執行的

假設你要的到這樣的一個數組

$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 协议》，转载必须注明作者和本文链接