Ask Your Question

replicate recursive sum

asked 2022-03-04 18:44:05 +0200

mahmood gravatar image

updated 2022-03-05 22:08:37 +0200

Emmanuel Charpentier gravatar image

i have a function defined as

image description

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)

thanks in advance

edit retag flag offensive close merge delete


Welcome to Ask Sage! Thank you for your question.

slelievre gravatar imageslelievre ( 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

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

done replaced with a link, thanks

mahmood gravatar imagemahmood ( 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.

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-03-04 20:56:24 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2022-03-06 03:30:12 +0200

updated 2022-03-06 03:30:33 +0200

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

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



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...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 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.

John Palmieri gravatar imageJohn Palmieri ( 2022-03-06 18:33:25 +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-03-04 18:44:05 +0200

Seen: 182 times

Last updated: Mar 06 '22