# replicate recursive sum

i have a function defined as

https://imgur.com/a/SfF2Edl.png

how can i replicate this function in sagemath using the sum function? i know it can be done in pure python with recursion but then whats the point of sagemath and symbolic calculation?

what ive tried so far is:

 f(x) = 1 if x == 0 else sum(1+f(j-1), j, 0, x-1) 

but i get the following error:

 NameError: name 'f' is not defined 

now i know its not possible to use recursion on a variable like this but there must be some tricky way to go about doing that (i hope so and thats why im here)

edit retag close merge delete

( 2022-03-04 18:46:06 +0200 )edit

To post links as a new user, insert spaces in them, and someone with enough "karma" can fix them.

Something like: https ://example .com

( 2022-03-04 18:47:01 +0200 )edit

done replaced with a link, thanks

( 2022-03-04 18:51:36 +0200 )edit

Homework ?

If so, try to solve it yourself. One (big (fat)) hint : recurrence...

Another hint : try to write f as a pure Python function (probably horribly inefficient...) (or do it by hand on paper (or in your head)), then see what its value is for the few first positive integers. Illumination should ensue quickly, and the point of your (probable) homework is probably to prove what these numerical results hint at...

Yet another one : try to think of ways to write efficiently your Python function. There are lots of way to do it, and t's a good exercise...

Bonus question : what happens if x is not a non-negative integer ? What should you add to your Python implementation ?

Other bonus question : explain the error message returned by your first attempt.

( 2022-03-04 20:56:24 +0200 )edit

Sort by » oldest newest most voted

I don't know about using Sage's symbolic sum, but this seems to work (idea based on the documentation for Sage's function, obtained by looking at function?and also at https://doc.sagemath.org/html/en/refe...):

sage: def ev(self, x):
....:     if x == 0:
....:         return 1
....:     else:
....:         return sum(1+self(j) for j in range(x))
....:
sage: f = function("f", nargs=1, eval_func=ev)

more

2

Possible slight refinements (and a slight fix) of John's solution :

def f_ev(self, x):
"""
A recursively defined symbolic function.

Do not return anything for non-numeric argument : the expression will
be returned unmodified.
"""
if SR(x).is_numeric():
if x in NN and x >= 0:
if x == 0:
return 1
return 1 + sum(self(j) for j in range(x))
return SR(float("nan"))


which allows for :

sage: {u:f(u) for u in list(range(5))+[x, 3/2]}
{0: 1, 1: 2, 2: 4, 3: 8, 4: 16, x: f(x), 3/2: NaN}


Now, you may be interested to attack the questions I raised in my previous comment...

( 2022-03-06 09:40:21 +0200 )edit

Good fix on the sum part. I mistakenly based mine on the code in the question rather than the actual function in the picture.

( 2022-03-06 18:33:25 +0200 )edit