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

Question

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

Ritualist

I.e., an equivalent to Haskell's iterate function. iterate (\x -> x + 1) 0 = 0, 1, 2, 3, 4, 5, ... – Triton

@Triton iterate in combination with takeWhile. – Mellow

I never know what to do with questions which are just "does X exist?" and I'm confident the answer is "No". There's nothing I can do to justify that answer other than link to the documentation you've already linked. – Jessicajessie

@SvenMarnach True. I was focusing on the part missing from itertools, but you do need the combination of iterate and {take,drop}while. – Triton

@DSM, yeah, I know existence questions have the problem that negative answers are essentially unprovable. But as I'm particularly interested in what the standard library has to offer here, I didn't know how to put my question differently. – Ritualist

@SvenMarnach: Why did you remove your answer? I didn't have time to test it before it disappeared, but it did look promising. – Ritualist

I removed it because it was wrong. Unfixably wrong. – Mellow

Answer 1

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.

Throat

It's usually called iterate, e.g. in Haskell or in this functional Python library. – Mellow

Unfortunately, I think "iterate" in Python is pretty closely tied to iter, which is more about stepping thru a sequence, rather than recursively applying a stepping function to an item to get the next item. But by whatever name, I think itertools would be a good home for something like this. – Throat

Where is the generator expression? – Picket

@StefanPochmann The function recur_to_gen() is a generator function (since it yields). There is no generator expression here. – Mellow

@SvenMarnach: I think SP was drawing attention to PM's first sentence-- the OP's original function (though called recur) is non-recursive, and already a genfunc. – Jessicajessie

Sorry, I mentally equate a call to a generator with a generator expression, but that is sloppy terminology on my part. @SvenMarnach is correct. – Throat

Edited, hopefully for the better in terminological precision. – Throat

@PaulMcGuire Yes, that's what I meant and it's fixed now. Now I just still think the OP's original is better, so I disagree with the "need" to do this :-) – Picket

@Jessicajessie - not recursive in the sense that it calls itself, but in that it iterates through a not-necessarily-contiguous chain of items by calling a stepping function on the current item in order to get the next. – Throat

@StefanPochmann - I like the separation of the "give me the sequence of items found by next_item = step_function(current_item)" from the predicate testing (as the OP has combined into one). With recur_to_gen or iterate or recur, you convert this chain of items into a sequence that could then be used for takewhile'ing, groupby'ing, or any other itertool that works with an iterator. – Throat

I'll edit my question to also allow accepting no predicate, as that's indeed covered by itertools.takewhile. – Ritualist

Concerning the function name: I've chosen recur in the question, to reflect that the function implements a sequence produced by a recursively defined recurrence, even if the implementation is iterative, not recursive. Though, as the English verb 'recur' exists and has a somewhat different meaning, I don't think that name can be used for proposing a function like this to be included in itertools. – Ritualist

Answer 2

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).

Freeboot

Heh, I had just started my other computer which has Python 3.4 to test something similar to this shortly before I saw your answer. – Ritualist

Answer 3

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.)

Triton

The latest available build is for Python 2.5. A newer functional package for Python: github.com/kachayev/fn.py – Mellow

It still works (installed via pip, but I didn't test it extensively) but yes, I think functional was a one-off proof-of-concept that was never really supported. – Triton