CODEWITHSUNDEEP
pythonrecursionpython-itertoolsrecurrencefunctools
das-g
das-g

Reputation: 9994

Does Python have an iterative recursion generator function for first-order recurrence relations?

Is there a built in function or standard library function roughly equivalent to

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

or

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

or even just

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

in any version of Python? (The latter is as good as the other two when combined with itertools.takewhile.)

A generator function like these would allow to compute certain recursively defined sequences iteratively, namely first-order recurrence relations.

While these aren't too hard to implement when needed, I feel like something like them should be part of itertools or maybe functools, but if it is, I haven't been able to spot it in the documentation, yet.

Usage examples:

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

Should also work with non-number elements:

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)']

Upvotes: 7

Views: 764

Answers (3)

Copperfield
Copperfield

Reputation: 8510

In Python 3.3+, the new itertools.accumulate can be used to this purpose in combination with the other itertools

For example:

>>> 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 takes a sequence and a function with 2 arguments: The first is the accumulate value and the second is the next value in the sequence. In this case, we only need the first argument, which will be the first element of the sequence passed to accumulate for the first call of the passed function and the return value of that function for subsequent calls.

Thus, we only need the start of the passed sequence to be our initial value — 2 in this case. The content of the rest of the sequence is irrelevant, but we can use it's length to control how many elements we want (as in the first example) or to create an infinite generator (like the second example).

Upvotes: 5

PaulMcG
PaulMcG

Reputation: 63709

The missing link is that you need something to convert your recursive stepping function into a generator. Once you have that, then you can use any of the itertools methods.

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 is probably a reasonable thing to propose adding to itertools.

Upvotes: 4

chepner
chepner

Reputation: 531075

The functional package provides the pieces to simulate this.

from functional import dropWhile, iterate    
recur = dropWhile(predicate, iterate(step_func, start))

For example,

>>> next(dropWhile(lambda x : x < 10, iterate(lambda x: x + 1, 2)))
10

(dropWhile isn't really any different from itertools.dropwhile.)

Upvotes: 3

Related Questions