- 中文名
- 递归算法
- 外文名
- recursive algorithm [4]
recursion algorithm [5]
- 属 性
- 计算机算法
- 实现过程
- 一般通过函数或子过程来实现
- 特 点
- 递归就是在过程或函数里调用自身
简介
播报编辑
递归算法应用的场景是要解决的问题和其子问题具有相似性的时候，通过直接或间接的调用自己求出问题解的方法。它是通过解决一个问题的更小实例来解决一个大的问题的解的算法。递归算法有两个过程，一是调用过程，二是向上传递结果的过程。 [3]
递归程序
播报编辑
(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程序同样计算一个数字的阶乘，但是使用尾部递归： [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
这一定义相当于宣告“一个链表或是空串列，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。 [2]
