递归函数

递归

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

一个_递归函数_至少需要一个_基准情况_和一个_递归情况_。

基准情况在不再次调用函数的情况下返回一个值。 递归情况会再次调用函数，并修改输入，使其最终能够匹配基准情况。

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

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(...)]。 在底层，有些内置函数就是用递归实现的。