Intermediate results from recursion

Question

I have a problem where I need to produce something which is naturally computed recursively, but where I also need to be able to interrogate the intermediate steps in the recursion if needed.

I know I can do this by passing and mutating a list or similar structure. However, this looks ugly to me and I'm sure there must be a neater way, e.g. using generators. What I would ideally love to be able to do is something like:

intermediate_results = [f(x) for x in range(T)]
final_result = intermediate_results[T-1]

in an efficient way. While my solution is not performance critical, I can't justify the massive amount of redundant effort in that first line. It looks to me like a generator would be perfect for this except for the fact that f is fundamentally much more suited to recursion in my case (which at least in my mind is the complete opposite of a generator, but maybe I'm just not thinking far enough outside of the box).

Is there a neat Pythonic way of doing something like this that I just don't know about, or do I just need to just capitulate and pollute my function f by passing it an intermediate_results list which I then mutate as a side-effect?

Answer 1

I have a generic solution for you using a decorator. We create a Memoize class which stores the results of previous times the function is executed (including in recursive calls). If the arguments given have already been seen, the cached versions are used to quickly lookup the result.

The custom class has the benefit over an lru_cache in that you can see the results.

from functools import wraps

class Memoize:
    def __init__(self):
        self.store = {}

    def save(self, fun):
        @wraps(fun)
        def wrapper(*args):
            if args not in self.store:
                self.store[args] = fun(*args)
            return self.store[args]
        return wrapper

m = Memoize()

@m.save
def fibo(n):
    if n <= 0: return 0
    elif n == 1: return 1
    else: return fibo(n-1) + fibo(n-2)

Then after running different things you can see what the cache contains. When you run future function calls, m.store will be used as a lookup so calculation doesn't need to be redone.

>>> f(8)
21
>>> m.store
{(1,): 1,
 (0,): 0,
 (2,): 1,
 (3,): 2,
 (4,): 3,
 (5,): 5,
 (6,): 8,
 (7,): 13,
 (8,): 21}

You could modify the save function to use the name of the function and the args as the key, so that multiple function results can be stored in the same Memoize class.