# Recursion directly in a list

I would like to know if there is a way to create a recursion directly in a list. The following command doesn't work

f(x) = -(x-4)^2+16
g(x) = f(x)-f(0)
d=[x for x in range(9)]
s=[(c[i]-c[i-1])/d[i]-d[i-1] for i in range(1,len(c))]
g=[d[i]-d[i-1] for i in range(1,len(d))]
h=[0 if (i<1) else   h[i-1] + g[i] for i in range(len(d)-1) ]

edit retag close merge delete

As written, the definitions of f(x), g(x), c, and s are not used in the final result. The definition of d can be simplified to d = range(9). The line g = [d[i]-d[i-1] for i in range(1,len(d))] is just taking differences of consecutive integers (the entries of range(9)), so every entry of the list g is 1. So the code could be simplified to two lines: g = [1] * 9 and (the broken line) h = [...]. Max Alekseyev's answer is a quick way to use recursion on the entries of the list g.

( 2022-08-28 02:38:30 +0100 )edit

@john-palmieri i guess that the provided example is only a minimal example to show the issue, otherwise, one could simply put h=range(8) (or list(range(9))) from scratch. In particular, is it not clear to me whether h is supposed to be more complex than just accumulating sums from g.

( 2022-08-28 19:42:38 +0100 )edit

@tmonteil. Right, I understand, although for a minimal example, it's far from minimal.

( 2022-08-28 21:36:11 +0100 )edit

Sort by » oldest newest most voted

This can be done via Python's itertools.accumulate function:

import itertools
h = list( itertools.accumulate(g, initial=0) )

more

In your last line, you use h to define h itself.

EDIT (given the explanation provided in comments): it is not possible to do such a thing. Indeed, when you write h=[...], the Python name h is created after the object [...] is created.

So, you have to define a recursive function as follows:

sage: def hh(i):
....:     if i<1:
....:         return 0
....:     else:
....:         return hh(i-1) + g[i]
....:
sage: h = [hh(i) for i in range(len(d)-1)]
sage: h
[0, 1, 2, 3, 4, 5, 6, 7]


That said, i guess (i might be wrong in your motivation), that you wanted to use a list so that when you compute h[4], you do not have to do the whole recursion by computing h[3], h[2], h[1], h[0] again, which is what hh does. The trick is to use the @cached_function decorator, that computes h[i] only once and memoizes the result for further calls. So, you can do:

sage: @cached_function
....: def hh(i):
....:     if i<1:
....:         return 0
....:     else:
....:         return hh(i-1) + g[i]
....:
sage: h = [hh(i) for i in range(len(d)-1)]
sage: h
[0, 1, 2, 3, 4, 5, 6, 7]

more

I know. What I ask is : is there a procedure which permit to define a recursion in a vector.

( 2022-08-27 11:14:29 +0100 )edit