遞歸和迭代

有什麼區別？這些都一樣嗎？如果沒有，有人可以給我一個例子嗎？遞歸和迭代

MW：迭代-1：迭代或重複的動作或過程：作爲a：一系列操作的重複產生連續接近期望結果的結果的過程b：重複計算機指令指定次數或直到滿足條件

Recusion - 3：涉及使用調用自身一次或多次直到指定條件爲止的過程，子例程，函數或算法的計算機編程技術在這段時間裏，每次重複的其餘部分都從最後一個被調用到第一個處理

2010-04-05 Strawberry

不同之處在於遞歸爲您提供了一個堆棧，無需索取一個堆棧。如果你需要一個，迭代讓你問一個。其他一切都是奇怪的。 – CandiedOrange 2017-05-27 04:42:27

我們可以從recursive and iterative processes中區分（如在SICP中完成的）遞歸和迭代過程。前者與你的定義所描述的一樣，其中遞歸基本上與數學recursion相同：根據其自身定義a recursive procedure。迭代過程用循環語句重複一段代碼。但是，遞歸過程是一個非常量（例如O(n) or O(lg(n)) space）執行，而迭代過程需要O（1）（常量）空間。

對於數學實例中，所述斐波那契數是遞歸定義：

Fibonacci function

Sigma notation類似於迭代：

$harmonic number$

原樣Pi notation。類似於一些（數學）遞歸公式可以被重寫爲迭代公式，一些（但不是全部）遞歸流程具有迭代等價物。所有遞歸過程都可以通過跟蹤自己數據結構中的部分結果而不是使用函數調用堆棧來轉換爲迭代過程。

來源

2010-04-05 05:19:45 outis

我喜歡這個答案的大部分，但我不同意遞歸意味着非恆定空間。 http://en.literateprograms.org/Fibonacci_numbers_%28Scheme%29比較「直接」和尾遞歸方法。根據上述定義，鏈接中的尾遞歸函數不是遞歸的： -/ – 2010-04-05 23:34:44

@pst：我認爲你錯過了這一點。使用尾遞歸的函數是一個遞歸過程，並生成一個迭代過程。遞歸進程根據定義使用非恆定空間。 – outis 2010-04-06 01:23:38

@outis：不要讓你很好...... 首先你說r＆i PROCEDURES與r＆i PROCESSES不同。一個是空間不變，另一個不是。瞭解。然後你說迭代過程循環，而迭代過程在空間中是恆定的。 i PROCEDURE和i PROCESS之間的區別是什麼？循環可以是恆定的，但不必。 – CoR 2012-06-07 23:39:10

這是一個Lisp函數找到列表的長度。它是遞歸：

(defun recursive-list-length (L) 
    "A recursive implementation of list-length." 
    (if (null L) 
     0 
    (1+ (recursive-list-length (rest L)))))

它讀取「的列表的長度是0，如果該列表爲空，或1加開始與所述第二元件的子列表的長度）

而這是strlen的實現 - C函數找到一個空終止char*字符串的長度是迭代：

size_t strlen(const char *s) 
{ 
    size_t n; 

    n = 0; 
    while (*s++) 
     n++; 
    return(n); 
}

你的目標是重複一些操作使用迭代，你僱用一個明確的環（像。 while廁所p代碼中的strlen）。使用遞歸，你的函數使用（通常）更小的參數來調用自己，等等，直到符合邊界條件（上面代碼中的null L）。這也重複了操作，但沒有明確的循環。

來源

2010-04-05 05:02:27

根據你提到的定義，這兩個是非常不同的。在迭代中，沒有自我調用，但在遞歸中，函數自己調用

例如。對於階乘運算

fact=1 
For count=1 to n 
fact=fact*count 
end for

和遞歸版本

function factorial(n) 
if (n==1) return 1 
else 
n=n*factorial(n-1) 
end if 
end function

迭代算法通常

遞歸代碼更簡潔，但使用較大的內存量。有時，遞歸可以轉換爲使用dynamic programming.

來源

2010-04-05 05:03:16 Midhat

[快點特朗普這個！]迭代

一種形式可以轉換爲其他，但有一個明顯的限制：許多「流行」的語言（C/Java的/普通的Python）不支持TCO/TCE（tail-call-optimization/tail-call-elimination），因此每次一個方法遞歸地調用自己時，使用遞歸會'向堆棧添加額外的數據'。

所以在C和Java中，迭代是慣用的，而在Scheme或Haskell中，遞歸是慣用的。

來源

2010-04-05 05:07:08

對於上述的一個很好的例子，考慮用於深度優先搜索的遞歸與迭代過程。它可以通過遞歸函數調用使用語言特性完成，也可以在使用堆棧的迭代循環中完成，但該過程本身是遞歸的。

來源

2010-04-05 05:29:20

遞歸：例如：以斐波那契數列爲例。要得到任何斐波那契數字我們必須知道前一個。所以你會在每個小於給定的數字的情況下對相同的操作進行操作（同一個操作），並調用相同的方法。

FIB（5）=蛋白原（4）+ 5

FIB（4）=蛋白原（3）+ 4 。。即重複使用方法fib

迭代循環就像添加1 + 1 + 1 + 1 + 1（迭代添加）以獲得5或3 * 3 * 3 * 3 * 3（迭代相乘）以獲得3^5。

來源

2010-11-30 10:31:13 Aadishri

針對遞歸與非遞歸之間的區別; 遞歸實現有點更容易驗證的正確性; 非遞歸實現有點效率更高。

Algorithms (4th Edition)

來源

2017-05-27 03:52:56

回答

相關問題