Ask Your Question

Recursion directly in a list

asked 2022-08-27 09:31:35 +0200

Cyrille gravatar image

updated 2022-08-27 09:59:12 +0200

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)]
c= list(map_threaded(g,d))
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 flag offensive 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.

John Palmieri gravatar imageJohn Palmieri ( 2022-08-28 02:38:30 +0200 )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.

tmonteil gravatar imagetmonteil ( 2022-08-28 19:42:38 +0200 )edit

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

John Palmieri gravatar imageJohn Palmieri ( 2022-08-28 21:36:11 +0200 )edit

2 Answers

Sort by ยป oldest newest most voted

answered 2022-08-27 15:09:05 +0200

Max Alekseyev gravatar image

updated 2022-08-27 15:10:00 +0200

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

import itertools
h = list( itertools.accumulate(g, initial=0) )
edit flag offensive delete link more

answered 2022-08-27 10:37:06 +0200

tmonteil gravatar image

updated 2022-08-27 14:09:08 +0200

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]
edit flag offensive delete link more


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

Cyrille gravatar imageCyrille ( 2022-08-27 11:14:29 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2022-08-27 09:31:35 +0200

Seen: 28,355 times

Last updated: Aug 27 '22