我們時常會遇到一些計算規則，它們在定義一個序列的元素時，要用到序列中在它前面的元素。這時就有兩種不同的進行計算的辦法。第一個辦法是疊代，就是先算出第一個元素，再用遞推公式算出下面的元素。第二個辦法是遞歸，這個辦法初看起來是循環的，因為在定義一個過程時，用到了過程本身。讓我們用一些例子來說明遞歸與疊代的差別。
設我們想要計算 n！=1·2·3…（n-1）·n。顯然，這裡有一個遞推關系：n！=n·（n-1）！，還有初始值1！=1。做完了第一步以後，就能相繼地算出 2！，3！，4！等等，一直到算出 n！為止。另一個辦法是：把計算階乘作為一個程式，記作FACT，而用FACT（n）表示執行這個程式到n！的結果，于是FACT（n）=n×FACT（n-1），這就是一個遞歸程式。
第二個辦法是：為了知道如何得到n！，隻需知道如何得到（n-1）！，而為了知道如何得到（n-1）！，隻需知道如何得到（n-2）！，以此類推。因為1！=1，是以能得到n！。這樣，遞歸有點像是把疊代“倒過來”考慮。
從某些方面來說，用這個例子來說明這兩種程式的差别是太簡單了。此外，如果真要計算 n！，則疊代比遞歸更加簡單和自然。現在我們再看一個例子，這裡遞歸就比疊代簡單得多了。
梵天塔
梵天塔是盧卡斯（法國數學家）發明的一種數學遊戲，設有n個圓盤，大小不一，盤的中心是一個小洞，按大小把它們疊在一根小柱A上。大的放在下面。還有另外兩根空柱子B和C。問題是如何把原來在柱子A上的一摞圓盤移到柱子B，但要服從以下規則：每次隻許移動一個圓盤，每一次都隻能移動一根柱子最上面的圓盤放到另一根柱子上，此外任何時刻都不許把圓盤壓在較小的圓盤上。
如果隻有3個圓盤，這個問題是很容易的，但是當圓盤數目增加時，難度就快速增加了。然而借助于遞歸，就能很快地找到按照要求移動圓盤的算法了。 事實上，假設我們已經知道移動n-1個圓盤的程式H（n-1），則下面就是移動n個圓盤的程式 H（n）：先把小柱 A上的上面n-1個圓盤用程式H（n-1）移到小柱C上，再把A上的最後一個移到B上；最後再用H（n-1）把C上的n-1個圓盤全部按規則移到 B 上，而問題完全解決。我們可以把這個遞歸程式用符号寫為
很容易用歸納法得出，整個程式包含2^n - 1步，此外，還能得知，這個任務不可能以更少的步數來完成。是以步數必為n的指數函數，而對于大的n。這個程式是很長的。
更進一步說，n越大，就需要更多的存貯單元來追蹤我們的程式已經進行到哪一步了。與此相對照的是，如果我們想在疊代程式中實行一次疊代，我們隻需要知道上一步疊代的結果就夠了。是以，我們最需要記憶的隻是一次疊代的結果。對于梵天塔，确實也有一個疊代程式。描述這個程式很容易，但是，這個程式确實能解決問題，卻不是那麼明顯。它把這n個圓盤的位置編碼成為一個n位的序列，而在每一步都給出得到下一個 n 位序列的很簡單的規則。這個規則并不參照程式已經執行了多少步，是以，除了用來存貯圓盤位置外，所需記憶的量是很小的。
推廣的歐幾裡得算法
歐幾裡得算法是很容易可以自然化為遞歸的另一個例子。如果a和b是兩個正整數，則可以寫出a=qb＋r，0≤r<b。這個算法依據的是下面的觀察：gcd（a，b）=gcd（b，r）。因為餘數r很容易從a和b算出，又因為數對（b，r）小于數對（a，b），是以，這就給了一個遞歸程式，而在遇到（a，0）形式的數對時就會停止。
歐幾裡得算法的一個重要推廣是貝祖引理。這個引理指出，對于任意一對正整數 a 和 b，一定存在一對整數（不一定都為正）u和v，使得
怎樣去求這種整數u，v呢？推廣的歐幾裡得算法給出了答案，而它又是可以由遞歸來定義的。設對于b和r，能夠找到一對（u'，v'）使得
則因a=bg＋r，可以把r=a-qb代入上式，而得
這樣，若令u=v'，v=u'-v'q，就得到了d=ua＋ub。因為對于a和b所需的數對（u，n）可以容易地從較小的b和r所需的（u'，v'）算出。這就給了一個遞歸程式。r=0就是遞歸的"底"，這樣就有1b＋0r=d。一旦到了這時，就可以“往回走”，通過歐幾裡得算法，按照上面的規則逐漸修改（u，v）。
複雜性
迄今我們都是作為理論來讨論算法，而忽略了它的實用性。然而，單是有算法存在，還不一定能保證計算機能夠執行它，因為有些算法包含的步數如此之多，使得沒有一種計算機能夠執行。一種算法的複雜性，粗略地說，就是它完成一項任務所需的步數。更準确地說，這是算法的時間複雜性。還有空間複雜性，是指為了執行這個任務所需的存貯的多少。複雜性理論研究的就是完成各種任務所需的計算機資源。
歐幾裡得算法的複雜性
計算機執行歐幾裡得算法所需的時間與計算商和餘數所需的時間密切相關，也就是與遞歸程式通路其自身的次數密切相關。當然，這個數進一步又依賴于想要求其 gcd 的數 a和b的大小。一個初始的觀察是：如果 0<b≤ a，則 a 除以 b 的餘數必小于a/2。由此可知，在求餘數時，隻要計算了兩步，就可以得到一個數對，而其第一個分量最多隻有原來的第一個分量的一半，由此容易看到，計算餘數最多隻需要
而此數大體上與a的位數成正比。因為一個數的位數遠小于此數本身，這個算法可以很容易地用于很大的數，這就使它除有理論意義外，還有很大的實用性。
所需除法的次數，在最壞的情況下是多少，這個問題直到19世紀上半葉才有人研究。上面給出的界限是由芬克在1841年得出的。但是不難看到，這個結果可以稍加改善，而證明當a和b是斐波那契數列的相繼兩項時，算法最長。這意味着所需除法的數目絕不會超過
歐幾裡得算法還有很低的空間複雜性。當把數對（a，b）代以數對（b，r）後，就可以忘掉原來的數對，是以在任何階段都不必記住很多東西（也就是不必把它放在計算機的存貯内）。與此相對照，推廣的歐幾裡得算法表面上看，需要記住導緻 a 和b的gcd d的全部計算過程，因為這樣就可以做一系列代入以得出u和v使得ya＋bu=d。但是仔細看一下，又可以看出，在任何時刻，隻需記住少數幾步就可以完成這個工作。
讓我們用一個例子來說明這是怎麼做的。我們設 a= 38，b= 21，很明顯gcd（38，21）=1。現在要找出u和v使得38u＋21v=1。
- 我們從寫出歐幾裡得算法的第一步開始：38=1×21＋17。這一步告訴我們17=38-21。
- 再作第二步：21=1×17＋4。我們已經知道了如何用38和21表示17，把它代入上式，就有21=1×(38-21)＋4。
- 移項以後可得4=2×21-38。現在再來作歐幾裡得算法的第三步：17=4×4＋1。
- 隻要記住第一步和第二步的結果，就可以把17和4都用38和21表示，是以再代入一次就有38-21=4×(2×21-38)＋1。
- 整理以後就有1=5×38-9×21，而問題完全解決。
可見隻需記住兩步的結果。
想一想這個過程就會看到，在每一階段都隻需要記住某兩個數（例如上面的17 和 4）是怎樣用 a 和b 表示的。是以推廣的歐幾裡得算法，如果适當執行，其空間複雜性也是很小的。