Python Decorator to avoid recursion limit on recursive functions

memoize_python_recursion.md

I built a decorator with the memoize idea: it will take care of your system recursion limit, and avoid it by splitting calculation in batches that are as large as the system can offer. It will also of course remember all the values for easy retrieval

Short working version:

import sys
from math import floor, ceil

def memoize(f):
    memo = [None]
    limit = sys.getrecursionlimit()
    limit = floor(limit/2 - 3)
    limit_list = [None] * limit

    def handler(x):
        reps = ceil((x-max(limit,len(memo)-1))/limit)
        for i in range(reps):
            if memo[len(memo)-1] is not None or len(memo)-1 == 0:
                memo.extend(limit_list)
            x_i = len(memo) - 1
            handler(x_i)
        if x - (len(memo)-1) > 0:
            memo.extend(limit_list)
        if memo[x] is None:
            memo[x] = f(x)
        return memo[x]
    return handler

You can then run it:

@memoize
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)


print(fib(1000))

Result: 42246963333923048787067256023414..

Explained version:

import sys
from math import floor, ceil

def memoize(f):
    memo = [None]
    limit = sys.getrecursionlimit()
    # now divide it because we are adding double layer here
    # a function of a function..
    limit = floor(limit/2 - 3)
    limit_list = [None] * limit
    print(f'limit: {limit}')

    def handler(x):
        reps = ceil((x-max(limit,len(memo)-1))/limit)
        for i in range(reps):
            print(f'rep {i+1} of {reps}')
            print(f'x: {x}\nmemo: {len(memo)-1}')
            if memo[len(memo)-1] is not None or len(memo)-1 == 0:
                # only do this if the list is not to be checked
                # for example a previous calculation has given
                # a calculation up to 50, but the limit is 70
                # so the values from 50 to 70 are [None]
                # so we need not to extend the list, but to check
                # the elements from 0 to 70 (the last batch)
                memo.extend(limit_list)
            print(memo)
            # len(memo) changes each time,
            # so each iteration the recursion limit gets added
            x_i = len(memo) - 1
            print(f'x_{i+1}: {x_i}')
            handler(x_i)
            if i+1 == reps:
                print(f'Final step: from {x_i} to {x}')

        if x - (len(memo)-1) > 0:
            memo.extend(limit_list)

        if memo[x] is None:
            memo[x] = f(x)
        return memo[x]

    return handler

It even uses memory to avoid going back when calling it again!

print(fib(1000))
print(fib(2000))

This is the output:

limit: 497
rep 1 of 2
x: 1000
memo: 0
x_1: 497
rep 2 of 2
x: 1000
memo: 497
x_2: 994
Final step: from 994 to 1000
434665576869374564356..
rep 1 of 2
x: 2000
memo: 1491
x_1: 1491
rep 2 of 2
x: 2000
memo: 1491
x_2: 1988
Final step: from 1988 to 2000
422469633339230487870672560..