# 遞迴 (電腦科學)

(重新導向自 Recursion)

## 遞迴程式

${\displaystyle \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))


## 能夠解決的問題

1、資料的定義是按遞迴定義的。如Fibonacci函式

2、問題解法按遞迴演算法實現。如Hanoi問題

3、資料的結構形式是按遞迴定義的。如二元樹、廣義表等。

## 遞迴資料

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 （英語）.