Create a list accumulating the results of calling a function repeatedly on an input value

Question

Is there a library function that creates recursive lists in the following sense,

recursive_list(f, x0, n) = [x0, f(x0), f(f(x0)), f(f(f(x0))), ...]

with n elements in the returned list?

If not, how can this be written?

Answer 1

You could use itertools.accumulate, which works like reduce but gives you every intermediate value

def repeated_application(f_unary, x0, n):
    def f_binary(acc, _):
        return f_unary(acc)
    return itertools.accumulate(range(n), f_binary, initial=x0)

You just have to turn the unary function into a binary one.

Note, this returns an iterator (more general that way).

Also, the way n is supposed to work is underspecified, you can twiddle with it to fit your requirements

I also want to point out, the straightforward way using basic language constructs is perfectly acceptable;

def recursive_application(f, x0, n):
    acc = x0
    result = [acc]
    for _ in range(n):
        acc = f(acc)
        result.append(acc)
    return result

Or as a generator, it's very clean:

def repeated_application(f, x0, n):
    acc = x0
    yield acc
    for _ in range(n):
        acc = f(acc)
        yield acc