第壹，遞歸算法
遞歸算法(英文:Recursion algorithm)是指通過將問題反復分解為同類子問題來解決問題的方法。遞歸方法可以用來解決許多計算機科學問題，因此它是計算機科學中壹個非常重要的概念。大多數編程語言都支持函數的自調用，其中函數可以自己遞歸調用。計算理論可以證明遞歸完全可以代替循環，所以很多函數式編程語言(比如Scheme)都是用遞歸來實現循環的。
二、遞歸程序
在支持自調優的編程語言中，遞歸可以通過簡單的函數調用來完成。例如，計算階乘的程序在數學上可以定義為:
這個程序可以用Scheme語言編寫:
1
(define(階乘n) (if (= n 0) 1 (* n(階乘(- n 1))))
定點組合子
即使壹種編程語言不支持自調用，如果壹個函數是這種語言中的第壹個類(也就是說，它可以在運行時創建，並被視為變量)，那麽遞歸就可以由定點組合子(英語)生成。下面的Scheme程序沒有使用自調用，而是使用了壹個叫做Z算子(英文:Z combinator)的定點合並器，所以也可以達到遞歸的目的。
1
(定義Z(lambda(f)((lambda(recurve)(f(lambda arg(apply(recurve recurve)arg))))(lambda(recurve)(f(lambda arg(apply(recurve recurve)arg)))))(定義事實(Z(lambda(f)(lambda(n)(if(& lt；= n 0) 1 (* n (f (- n 1))))))))
這個程序的思路是，既然函數在這裏不能調用自己，那麽我們可以用函數應用和Z結合得到的函數來應用要計算的參數。
尾部遞歸
尾遞歸是指遞歸函數在調用自身後直接返回值，不需要對其增加運算。尾遞歸相當於循環，在某些語言中(比如Scheme)可以優化為循環指令。因此，在這些語言中，尾遞歸不會占用調用堆棧空間。下面的Scheme程序也計算壹個數的階乘，但是使用尾部遞歸:
1
(define(階乘n) (define (iter乘積計數器)(if(& gt；counter n)乘積(ITER(* counter product)(+counter 1)))(ITER 1 1))
第三，可以解決的問題
數據是遞歸定義的。比如斐波那契函數。
通過遞歸算法實現了問題的求解。比如河內問題。
數據的結構是遞歸定義的。如二叉樹、廣義表等。
第四，遞歸數據
數據類型可以用遞歸來定義，比如壹個簡單的遞歸定義為自然數的定義:“壹個自然數等於0或者另壹個自然數加1”。Haskell可以將鏈表定義為:
1
data list of strings = EmptyList | Cons String list of strings
這個定義相當於聲明“壹個鏈表或壹個空字符串列，或者壹個鏈表前面有壹個字符串”。可以看出，這個遞歸定義可以到達所有的鏈表。