trampoline.tyler.py

'''
see:
- https://eli.thegreenplace.net/2017/on-recursion-continuations-and-trampolines/
- https://gist.github.com/tylerbrandt/6411f874630aebb0e4ed9b075d6f8d08
'''
import sys
import inspect
#sys.setrecursionlimit(10)

def identity(x):
    return x

def trampoline(f):
    def wrapped(*args):
        res = f(*args)
        print(f"current recursion depth before unwrapping: {len(inspect.stack(0))}")
        while hasattr(res, '__call__'):
            print("unwrapping...")
            res = res()
        print(f"current recursion depth after unwrapping: {len(inspect.stack(0))}")
        return res

    return wrapped

class Solution(object):
    # Problem: decorating the thunk causes the trampoline to be called from the thunk, thus evaluating the thunk.
    @trampoline
    def uniquePaths(self, m, n, cont=identity):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        print("m={},n={}".format(m, n))
        if m == 1 or n == 1:
            return cont(1)
        return lambda: self.uniquePaths(m-1, n, lambda x: self.uniquePaths(m, n-1, lambda y: cont(x + y)))

if __name__ == "__main__":
  Solution().uniquePaths(4, 3)
  #Solution().uniquePaths(23, 12)