Does Python have an iterative recursion generator function for first-order repeat relationships?

Question

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

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 in combination with itertools.takewhile .)

Such a generator function will allow iteratively calculated certain recursively defined sequences, namely, first-order repetition relationships.

Although this is not so difficult to implement when necessary, I feel that something like them should be part of itertools or maybe functools , but if so, I have not yet been able to find it in the documentation.

---

Examples of using:

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

You should also work with elements other than the number:

 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

Invalid reference - you need something to convert your recursive step function to a generator. After that, 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 wise to suggest adding to itertools .

Answer 2

In Python 3.3+, the new itertools.accumulate can be used for this purpose in combination with 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 two arguments: the first is the accumulation 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 transferred function and the return value of this function for subsequent calls.

Thus, we only need the beginning of the passed sequence to be our initial value - 2 in this case. The content of the rest of the sequence does not matter, but we can use its length to control the number of elements we want (as in the first example), or to create an infinite generator (for example, the second example).

Answer 3

The functional package provides parts 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 is actually no different from itertools.dropwhile .)