递归程序

在支持自调用的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：

这一程序在Scheme语言中可以写作：

(define (factorialn)(if (= n0)1(* n(factorial(- n1)))))

不动点组合子

即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z 算子（英语：Z combinator）的不动点组合子，因此同样能达到递归的目的。

(define Z(lambda (f)((lambda (recur)(f(lambda arg(apply (recurrecur)arg))))(lambda (recur)(f(lambda arg(apply (recurrecur)arg)))))))(define fact(Z(lambda (f)(lambda (n)(if (<= n0)1(* n(f(- n1))))))))

这一程序思路是，既然在这里函数不能调用其自身，我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。

尾部递归

尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：

(define (factorialn)(define (iterproductcounter)(if (> countern)product(iter(* counterproduct)(+ counter1))))(iter11))

能够解决的问题

1、数据的定义是按递归定义的。如Fibonacci函数。

2、问题解法按递归算法实现。如Hanoi问题。

3、数据的结构形式是按递归定义的。如二叉树、广义表等。

递归数据

数据类型可以通过递归来进行定义，比如一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义链表为：

dataListOfStrings=EmptyList|ConsStringListOfStrings

这一定义相当于宣告“一个链表或是空串列，或是一个链表之前加上一个字符串”。可以看出所有链表都可以通过这一递归定义来达到。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。