Recursion 入门

递归是指根据自身定义的东西。在编程环境中,它是使用自称函数或递归类型的实践。

递归函数

递归函数有两个部分:

  • 一个或多个基本案例
  • 递归步骤

因为递归函数调用自身,所以函数调用字符串可以永远继续。为了确保函数终止必须包含基本情况。这些将告诉函数何时返回值而不是执行另一个递归调用。通常,递归函数将检查它们对基本情况的输入,并在达到基本情况时返回。如果尚未到达基本情况,则该函数将进入递归步骤。

递归步骤是函数调用自身的时间。许多递归函数将返回对递归调用的结果执行的一些计算。Fibonacci 序列示例证明了这一点。该函数递归调用自身两次,然后返回这些调用的结果总和

递归的一个常见用途是在大型数据结构(例如树和图形)上导航和执行计算。这很有效,因为递归可以解决问题并解决较小的问题,并以解决更大问题的解决方案为基础。递归的另一个常见用途是在没有内置循环结构的语言(通常是函数语言)中执行迭代操作(循环)。

递归类型

递归类型的值是由相同类型的值组成的,或者表达方式不同:递归类型是根据自身定义的。例如,列表是递归类型,因为列表的每个子集本身都是一个列表。树是另一个例子,因为节点从树中移除,剩下的构造仍然是树。

形式上,递归类型 T 的值集将由表单上的递归集方程式定义:

T = …… T …

递归集方程可以有许多解,但是这样的方程总是具有最小解,其是每个其他解的子集。

作为一个实际例子,考虑这个 Haskell 定义的列表类型,

data List a = Nil | Cons a (List a)

意思是 a 的列表是空列表或包含’a’(列表的头部)和另一个列表(尾部)的 cons 单元。