Menu
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.
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)']
704
Python also accepts function recursion, which means a defined function can call itself. Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result.
The important thing to note in this example is: the generator function recursively calls itself in a for loop, which sees an iterator and automatically uses the iteration protocol on it, so it actually gets values from it.
Since Python does not store anything about previous iteration steps, iteration is quite faster and memory-efficient than recursion.
Recursion in Python When you call a function in Python, the interpreter creates a new local namespace so that names defined within that function don’t collide with identical names defined elsewhere.
Since Python does not store anything about previous iteration steps, iteration is quite faster and memory-efficient than recursion. In practice, almost all iterations can be performed by recursions and vice-versa. Some tasks can be executed by recursion simpler than iteration due to repeatedly calling the same function.
A complicated function can be split down into smaller sub-problems utilizing recursion. Sequence creation is simpler through recursion than utilizing any nested iteration. Recursive functions render the code look simple and effective.
The reason your recursive call only executes once is that you are essentially creating nested generators. That is, you are creating a new generator inside a generator each time you call the function recursive_generator recursively. Try the following and you will see.
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).
160
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
