Tail recursion with a simple decorator api.
Project description
Use the tail_recursive
decorator to simply define tail recursive functions.
If you are encountering maximum recursion depth errors or out-of-memory crashes tail recursion can be a helpful strategy.
Example
import tail_recursive from tail_recursive
# Pick a larger value if n is below your system's recursion limit.
x = 5000
def factorial_without_tail_recursion(n, accumulator=1):
if n == 1:
return accumulator
return factorial_without_tail_recursion(n - 1, n * accumulator)
try:
# This will exceed the maximum recursion depth.
factorial_without_tail_recursion(x)
except RecursionError:
pass
@tail_recursive
def factorial(n, accumulator=1):
if n == 1:
return accumulator
# It is important that you return the return value of the `tail_call`
# method for tail recursion to take effect!
return factorial.tail_call(n - 1, n * accumulator)
# Implementation with tail recursion succeeds because the function is
# called sequentially under the hood.
factorial(x)
The tail_call
method returns an object which stores a function (e.g. factorial
) and
its arguments. The function is then lazily evaluated once the object has been returned
from the caller function (in this case also factorial
). This means that the
resources in the caller function's scope are free to be garbage collected and that its
frame is popped from the call stack before we push the returned function on.
Other Packages
Check out tco for an alternative api with extra functionality.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for tail_recursive-1.1.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a3ab6f6a11e4493be565a1e99cbbdce4945414c5d89ec526ceff1894293ab4d9 |
|
MD5 | 4172edaa8368854367730e1571d41eee |
|
BLAKE2b-256 | ec03ea977f5377dc9a27babe767342762b64b01329bdc1f2b2fcea0ffd3a103b |