递归 属于

关于 递归

递归函数是调用自身的函数。

一个递归函数至少需要一个基线条件和一个递归条件。

基线条件在不再调用函数的情况下返回一个值。 递归条件会再次调用函数，并修改输入，使其在某个时刻能够匹配基线条件。

下面是一个统计数组元素个数的例子。

def count:
  if length == 0 then
    0                       # base case
  else
    1 + (.[1:] | count)     # recursive case
  end;

([] | count),           # => 0
([11, 22, 33] | count)  # => 3

一个递归函数可以有很多基线条件，也可以有很多递归条件。 例如，斐波那契数列就是一个有两个基线条件的递归数列。

def fibonacci:
  if . == 0 then
    0
  elif . == 1 then
    1
  else
    (. - 1 | fibonacci) + (. - 2 | fibonacci)
  end;

10 | fibonacci          # => 55

统计数组中某个给定值x出现的次数，会用到两个递归条件。

def count_occurrences(x):
  if length == 0 then
    0
  elif first == x then
    1 + (.[1:] | count_occurrences(x))
  else
    (.[1:] | count_occurrences(x))
  end;

[11, 22, 33, 22, 44] | count_occurrences(22)    # => 2

在实践中，遍历数组以及其他可枚举的数据结构时，通常使用内置函数，比如map和reduce，或者使用流，例如[.[] | select(...)]。 在底层，一些内置函数就是用递归实现的。

无限递归

如果实现不当，递归函数可能永远无法返回结果。 这会带来问题，因为每次调用函数时，都会在内存中存下一个引用，记录虚拟机应当返回结果的位置（即在调用栈上）。 如果一个递归函数无限地调用自身，就可能耗尽内存，导致虚拟机因栈溢出错误而崩溃。

导致无限递归问题的原因可能包括：

• 忘记实现基线条件。
• 没有把基线条件定义为第一个分支。
• 进行递归调用时没有正确修改参数，因而永远无法到达基线条件。

尾调用优化

正如维基百科所述：

尾调用是指作为过程最后一个动作执行的子程序调用。 如果尾调用的目标是同一个子程序，就称该子程序为尾递归。

看看上面实现的fibonacci。 它的递归条件调用了自身两次。 函数需要执行的最后一个动作是加法。 由于最后一个动作不是对自身的调用，所以这个函数是递归的，但不是尾递归。

一些语言实现了尾调用优化，这样尾调用就可以复用当前的栈帧，而不必在调用栈上新增一个栈帧。 这除了能防止可怕的栈溢出之外，还能带来性能上的好处。

jq确实实现了尾调用优化，但只针对零元函数。 利用这一点的方法是定义一个“内部”的零元函数，让它接收某种状态作为输入。 内部函数可以按需修改状态，并把新的状态传给尾递归调用。 外部函数创建初始状态，并把它传给内部函数，从而启动递归。

可以把目前计算出的数列作为状态的一部分，来实现尾递归版的fibonacci函数。

def fibonacci:
  def _fib:
    # input: {limit: number, series: array}
    if (.series | length - 1) >= .limit then
      .series[.limit]                                   # base case
    else
      .series += [.series[-1] + .series[-2]] | _fib     # recursive case
    end;
  {limit: ., series: [0, 1]} | _fib;

10 | fibonacci          # => 55