Python是否具有针对一阶递归关系的迭代递归生成器函数？

Question

是否有内置函数或标准库函数大致相当于

def recur_until(start, step_fu, stop_predicate=lambda _: False):
    current = start
    while not stop_predicate(current):
        yield current
        current = step_fu(current)

要么

def recur_while(start, step_fu, predicate=lambda _: True):
    current = start
    while predicate(current):
        yield current
        current = step_fu(current)

甚至只是

def recur(start, step_fu):
    current = start
    while True:
        yield current
        current = step_fu(current)

在任何版本的Python？(当与之结合时,后者与其他两个一样好itertools.takewhile.)

像这样的生成器函数将允许迭代地计算某些递归定义的序列,即一阶递归关系.

虽然这些在需要时不太难实现,但我觉得像他们这样的东西应该是itertools或者可能的functools一部分,但如果是的话,我还没有在文档中发现它.

---

用法示例:

list(recur_until(2, lambda x: x**2 - 1, lambda x: x > 1e4))
# [2, 3, 8, 63, 3968]

还应该使用非数字元素:

list(recur_until('', lambda x: '[{}]({})'.format(x, len(x)), lambda x: len(x) > 30))
# ['',
#  '[](0)',
#  '[[](0)](5)',
#  '[[[](0)](5)](10)',
#  '[[[[](0)](5)](10)](16)',
#  '[[[[[](0)](5)](10)](16)](22)']

Answer 1

在Python 3.3+中,新的itertools.accumulate可以与其他itertools一起用于此目的

例如:

>>> from itertools import accumulate, repeat, takewhile
>>> fun = accumulate(range(2, 10), lambda x, _: x**2 - 1)
>>> list(fun)
[2, 3, 8, 63, 3968, 15745023, 247905749270528, 61457260521381894004129398783]
>>> fun = takewhile(lambda y: y < 1e4, accumulate(repeat(2), lambda x, _: x**2 - 1))
>>> list(fun)
[2, 3, 8, 63, 3968]

accumulate采用带有2个参数的序列和函数:第一个是累加值,第二个是序列中的下一个值.在这种情况下,我们只需要第一个参数,它将是传递给accumulate传递函数的第一个调用的序列的第一个元素,以及后续调用的该函数的返回值.

因此,我们只需要将传递的序列的开头作为我们的初始值 - 2在这种情况下.序列其余部分的内容是无关紧要的,但我们可以使用它的长度来控制我们想要的元素数量(如第一个示例中所示)或创建无限生成器(如第二个示例).

Answer 2

缺少的链接是您需要一些东西来将递归步进函数转换为生成器。一旦你有了它，你就可以使用任何 itertools 方法。

def recur_to_gen(step_fu, current, sentinel=None):
    while current != sentinel:
        yield current
        current = step_fu(current)


matches = itertools.takewhile(predicate, recur_to_gen(step_fu, start))

recur_to_gen建议添加到 可能是合理的事情itertools。