遞迴 (電腦科學)
在支援自呼叫的程式語言中，遞迴可以通過簡單的函式呼叫來完成，如計算階乘的程式在數學上可以定義為：
fact
(
n
)
=
{
1
if
n
=
0
n
⋅
fact
(
n
−
1
)
if
n
>
0
{\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}}
這一程式在Scheme語言中可以寫作：
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
不動點組合子
編輯
主條目：不動點組合子
即使一個程式語言不支援自呼叫，如果在這語言中函式是頭等物件（即可以在執行期建立並作為變數處理），遞迴可以通過不動點組合子（英語：Fixed-point combinator）來產生。以下Scheme程式沒有用到自呼叫，但是利用了一個叫做Z 算子（英語：Z combinator）的不動點組合子，因此同樣能達到遞迴的目的。
(define Z
(lambda (f)
((lambda (recur) (f (lambda arg (apply (recur recur) arg))))
(lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))
(define fact
(Z (lambda (f)
(lambda (n)
(if (<= n 0)
1
(* n (f (- n 1))))))))
這一程式思路是，既然在這裡函式不能呼叫其自身，我們可以用 Z 組合子應用(application)這個函式後得到的函式再應用需計算的參數。
尾端遞迴
編輯
主條目：尾端遞迴
尾端遞迴是指遞迴函式在呼叫自身後直接傳回其值，而不對其再加運算。尾端遞迴與迴圈是等價的，而且在一些語言（如Scheme中）可以被優化為迴圈指令。
因此，在這些語言中尾端遞迴不會佔用呼叫堆疊空間。以下Scheme程式同樣計算一個數字的階乘，但是使用尾端遞迴：[5]
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))