Intermediate results from recursion

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.

You can use your existing solution that makes many "redundant" calls to f, but employ the use of function caching to save the results to previous calls to f. In other words, when f(x1) is called, it's input arguments and corresponding return values are saved, and the next time it is called, the result is simply pulled from the cache

see functools.lru_cache for the standard library solution to this

ie:

from functools import lru_cache

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

Note, however, f must be a pure function (no side-effects, 1-to-1 mapping) for this to work properly

Having considered your comments, I'll now try to give another perspective on the problem.

So, let's consider a concrete example:

def f(x):
    a = 2
    return g(x) + a if x != 0 else 0
def g(x):
    b = 1
    return h(x) - b
def h(x):
    c = 1/2
    return f(x-1)*(1+c)

I

First of all, it should be mentioned that (in our particular case) the algorithm has form of: f(x) = p(f(x - 1)) for some p. It follows that f(x) = p^x(f(0)) = p^x(0). That means we should just apply p to 0 x times to get the desired result, which can be done in an iterative process, so this can be written without recursion. Though I believe that your real case is much harder. Moreover, it would be too boring and uninformative to stop here)

II

Generally speaking, we can divide all possible solutions into two groups: the ones that require refactoring (i.e. rewriting functions f, g, h) and the ones that do not. I have little to offer from the latter one (and I don't think anyone can). Consider the following, however:

def fk(x, k):
    a = 2
    return k(gk(x, k) + a if x != 0 else 0)
def gk(x, k):
    b = 1
    return k(hk(x, k) - b)
def hk(x, k):
    c = 1/2
    return k(fk(x-1, k)*(1+c))

def printret(x):
    print(x)
    return x

f(4, printret) # see what happens

Inspired by continuation-passing style, but that's totally not it.

What's the point? It's something between your idea of passing a list to write down all the computations and memoizing. This k carries additional behavior with it, such as printing or writing to list (you can make a function that writes to some list, why not?). But if you look carefully you'll see that it lefts inner code of these functions practically untouched (only input and output to function are affected), so one can produce a decorator associated with a function like printret that does essentially the same thing for f, g, h.

• Pros: no need to modify code, much more flexible than passing a list, no additional work (like in memoizing).
• Cons: Impure (printing or modifying sth), not so flexible as we would like.

III

Now let's see how modifying function bodies can help. Don't be afraid of what's written below, take your time and play with that thing a little.

class Logger:
    def __init__(self, lst, cur_val):
        self.lst = lst
        self.cur_val = cur_val
    
    def bind(self, f):
        res = f(self.cur_val)
        return Logger([self.cur_val] + res.lst + self.lst, res.cur_val)
    
    def __repr__(self):
        return "Logger( " + repr({'value' : self.cur_val,'lst' : self.lst}) + " )" 

def unit(x):
    return Logger([], x)

# you can also play with lala
def lala(x):
    if x <= 0:
        return unit(1)
    else:
        return lala(x - 1).bind(lambda y: unit(2*y))


def f(x):
    a = 2
    if x == 0:
        return unit(0)
    else:
        return g(x).bind(lambda y: unit(y + a))
def g(x):
    b = 1
    return h(x).bind(lambda y: unit(y - b))
def h(x):
    c = 1/2
    return f(x-1).bind(lambda y: unit(y*(1+c)))

f(4) # see for yourself

Logger is called a monad. I'm not very familiar with this concept myself, but I guess I'm doing everything right) f, g, h are functions that take a number and return a Logger instance. Logger's bind takes in a function (like f) and returns Logger with new value (computed by f) and updated 'logs'. The key point - as I see it - is the ability to do whatever we want with collected functions in the order the resulting value was calculated.

Afterword

I'm not at all some kind of 'guru' of functional programming, I believe I'm missing a lot of things here. But what I've understood is that functional programming is about inversing the flow of the program. That's why, for instance, I totally agree with your opinion about generators being opposed to functional programming. When we use generator gen in, say, function func, we yield values one by one to func and func does sth with them in e.g. a loop. The functional approach would be to make gen a function taking func as a parameter and make func perform computations on 'yielded' values. It's like gen and func exchanged their places. So the flow is inversed! And there are plenty of other ways of inversing the flow. Monads are one of them.

itertools islice gets a generator, start value and stop value. it will give you the elements between the start value and stop value as a generator. if islice is not clear you can check the docs here https://docs.python.org/3/library/itertools.html

intermediate_result = map(f, range(T))
final_result = next(itertools.islice(intermediate_result, start=T-1, stop=T))