sum of squares recursion

Question

I have to write a recursive function sumSquares() that takes a non-negative (>= 0) integer n as a parameter and returns the sum of the squares of the numbers between 1 and n. Example:

>>>sumSquares(2)
5
>>>sumSquares(3)
14

This is what I have so far:

def sumSquares(n):
    if n==0:
        return 0
    else:
        return sumSquares(n-1)+sumSquares(n-1)

Can I also have an explanation of what you did, I'm still in the process of learning recursion, and it would help a lot. Thanks.

Solution 1

Say you represent your function by S(x), x>0

S(x) = 1^2 + 2^2 + ... x^2

this can be written as

S(x) = (1^2 + 2^2 + ...(x-1)^2 )+ x^2

S(x) = S(x-1) + x^2. 

Now for the program.

def sumSquares(n):
        return sumSquares(n-1)+ n*n

But the problem is this doesn't know when to stop. We have to give a base case that tells it when to stop.

You know that S(0) = 0 or S(1) = 1.

therefore

def sumSquares(n):
    assert n >= 0
    if (n == 0):
        return 0
    else:
        return sumSquares(n-1)+ n*n

Solution 2

Shouldn't that be

return n * n + sumSquares(n - 1)

Comments

[nneonneo]

Are you taking a class on "Python, but only using recursion"? Because all your questions are from that class...

[JamesSwift]

Recursion is two things: 1) A base case. 2) A recursive call of the function. You have the right idea, but a better base case would be n==1, since you don't care about 0. The else should be return n*n + sumSquares(n-1)

[Jason Schayer]

no we are just in the chapter for recursion, and im just struggling with it

[jfs]

assert n >= 0. pep-8 recommends spaces around operators: n == 0

[pogo]

@J.F.Sebastian: Thanks, edited it.

[John La Rooy]

assert does nothing if I run python -O mwahahahahah

[jfs]

@gnibbler: assert is for documentation purposes only, otherwise it should be: if n < 0: raise ValueError("Expected non-negative number, got %r" % (n,))

[John La Rooy]

@J.F.Sebastian, also for unittests. Typically you should never use -O for running unittests

[jfs]

@gnibbler: It makes sense to run tests with/without -O flag to make sure that assertions in the code do not produce undesirable side-effects. unittest framework doesn't use assert statement to implement its assert* methods.