PHP算法——遞歸算法

遞歸函數在日常項目中有很廣泛的用途，例如寫樹結構、遍歷目錄等，今天我們用一個簡單的遞歸demo來求斐波那契數列，並用圖解釋它運行的過程。

<?php
// 0 1 1 2 3 5 8 13 21 34
function demo($n) {

	$number = 0;

	if ($n <= 0) {
		$number = 0;

	} elseif ($n == 1) {
		$number = 1;

	} else {
		$number = demo($n-1)+demo($n-2);
	}

	return $number;
}

echo demo(4);

輸出結果：

3

該函數工作流程用圖表示：

此時：demo(4)會等待demo(3)和demo(2)的返回結果

demo(3) = demo(2) + demo(1)，demo(3)又會等待demo(2)和demo(1)的計算結果，

demo(2) = demo(1) + demo(0)

demo(1) = 1,demo(0) = 0

開始逐層返回結果

總的來說，遞歸函數，就是一個先遞後歸的過程。