簡介

Iterative Method中文翻譯作迭代法或疊代法,而在數學領域和電腦程式領域的定義有些不同,數學領域的迭代法指的是無法使用公式一次求解,而須反覆運算求出近似解;而在電腦程式雖然亦有反覆運算的含義,但一般指的是迴圈解。

迭代法透過設定一個初始值開始反覆運算,最後求出答案,是算是一種Bottom-Up的模式,通常會和遞迴作比較,實作方式簡易區分如下:

  • 迭代:使用迴圈實作。
  • 遞迴:函式推疊呼叫。

基本上相同的演算法如果能夠直接使用迴圈,因為不透過函式堆疊,效能會比較好。相對於迭代,遞迴就算是一種Top-Down的模式。以階乘為範例:

遞迴

function Factorial(n)
	if n == 1
		return 1
	return n * Factorial(n - 1)

遞迴的思考模式,求n階的時候當作n-1階已知,相乘即是答案,n-1的如何求在n階的時候無須理會,就像上級要交由下屬去處理的Top-Down模式。

迭代法

function Factorial(n)
	sum = 1
	for i = 1 to n
		sum = sum * i
	return sum

迭代的思考模式,則是單純的逐一處理後回傳,由於他沒有下屬,所以必須自己處理完後回報給上層的Bottom-Up模式。

網路上的資料,階乘兩種方式的效能比較

N Recursive Iterative
10 334 ticks 11 ticks
100 846 ticks 23 ticks
1000 3368 ticks 110 ticks
10000 9990 ticks 975 ticks
100000 stack overflow 9767 ticks
文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()