# 递归 (计算机科学)

（重定向自遞歸 (計算機科學)

## 遞迴程式

### java

public void recursiveTest(){
recursiveTest();  //自己调用自己，就叫递归
}


### python

def RecursiveTest():
RecursiveTest()  # 自己调用自己


## 应用

${\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. ^ 廖雪峰. 递归函数. [2018年8月18日11:19:21].
5. ^ 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. （原始内容存档于2018-03-09） （英语）.