# 递归 (计算机科学)

## 遞迴程式

$\operatorname{fact}(n) = \begin{cases} 1 & \mbox{if } n = 0 \\ n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 0 \\ \end{cases}$

(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))


### 不動點組合子

(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))))))))


### 尾端遞迴

(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))


## 遞迴資料

data ListOfStrings = EmptyList | Cons String ListOfStrings


## 註釋

1. ^ Graham, Ronald; Donald Knuth, Oren Patashnik. Concrete Mathematics. 1990. Chapter 1: Recurrent Problems （英文）.
2. ^ Epp, Susanna. Discrete Mathematics with Applications 2nd. 1995. 427 （英文）.
3. ^ Wirth, Niklaus. Algorithms + Data Structures = Programs. Prentice-Hall. 1976. 126 （英文）. "The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."
4. ^ Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press. 1996 [2011]. ISBN 0-262-01153-0 （英文）.