CODEWITHSUNDEEP
python
VPNTIME
VPNTIME

Reputation: 761

Trying to recursively add the square of numbers

def recursive_add(s):
    sum = 0
    if len(s) == 1:
        sum += s[0] ** 2
    else:
        recursive_add(s[1:])
        sum += s[0]**2
    return sum


s = [8, 6, 8, 4]

print recursive_add(s)

however, for some reason, 8 gets squared right away and 64 is returned, even though it should be the last number to be squared and added to sum.

Upvotes: 1

Views: 3410

Answers (6)

Deeptangshu Saha
Deeptangshu Saha

Reputation: 11

The answer was quite simple just add the recursive-add(s[1:]) to sum in else part:

def recursive_add(s):
    sum = 0
    if len(s) == 1:
        sum += int(s[0]) ** 2
    else:
        sum = sum+int(s[0])**2+recursive_add(s[1:])
    return sum
s = [8, 6, 8, 4]
print (recursive_add(s))

Upvotes: 1

Hailei
Hailei

Reputation: 42163

You can just:

def recursive_add(s):
    return s and (recursive_add(s[1:]) + s[0]**2) or 0

In your original code, the issue seems to be that recursive_add(s[1:]) doesn't share the same sum with recursive_add(s). The sums are different ones. Try this instead:

sum = 0

def recursive_add(s):
    global sum
    if len(s) == 1:
        sum += s[0] ** 2
    else:
        recursive_add(s[1:])
        sum += s[0]**2

s = [8, 6, 8, 4]

print recursive_add(s)

Upvotes: 2

steveha
steveha

Reputation: 76695

When you are trying to figure out why your program isn't working correctly, it is good to figure out exactly what it is doing. Here is an example of how to modify your program to show what it's really doing.

def recursive_add(s):
    print "DEBUG: recursive_add(%s)" % repr(s)
    sum = 0
    print "DEBUG: sum: %d" % sum
    if len(s) == 1:
        sum += s[0] ** 2
        print "DEBUG: sum: %d" % sum
    else:
        recursive_add(s[1:])
        sum += s[0]**2
        print "DEBUG: sum: %d" % sum
    return sum


s = [8, 6, 8, 4]

print "result: %d" % recursive_add(s)

When you run this, here is what you get:

DEBUG: recursive_add([8, 6, 8, 4])
DEBUG: sum: 0
DEBUG: recursive_add([6, 8, 4])
DEBUG: sum: 0
DEBUG: recursive_add([8, 4])
DEBUG: sum: 0
DEBUG: recursive_add([4])
DEBUG: sum: 0
DEBUG: sum: 16
DEBUG: sum: 64
DEBUG: sum: 36
DEBUG: sum: 64
result: 64

As you can see, your function does successfully snip the first number off the list, and calls itself recursively until it has handled all the numbers. But the problem is that you keep re-setting sum to 0, so sum isn't accumulating an actual sum; so your final answer is 0 + 64, or just 64.

Upvotes: 1

georg
georg

Reputation: 214949

First, an one-liner solution for your specific problem:

def rec_add(s):
    return s[0] * s[0] + rec_add(s[1:]) if s else 0

More advanced and abstract stuff follows.

In functional programming jargon, you "map" x**2 on a list and "fold" the list by adding its elements together. Python provides necessary primitives for that (map and reduce respectively) and the sum of squares can be simply written as:

from operator import add, mul

xs = [1,2,3,5]
print reduce(add, map(mul, xs, xs)) # 39

You can also combine map and fold steps in one function:

def map_and_fold(xs, mapfun, foldfun, init):
    if not xs:
        return init
    return foldfun(
        mapfun(xs[0]),
        map_and_fold(
            xs[1:], mapfun, foldfun, init))

and define sum_squares as a partial application of the above:

from functools import partial

sum_squares = partial(map_and_fold, 
    mapfun = lambda x: x * x,
    foldfun = lambda x, y: x + y,
    init = 0)

Test:

xs = [1,2,3,5]
print sum_squares(xs) # 39

More info: map, fold, partial application.

Upvotes: 3

MatthieuW
MatthieuW

Reputation: 2372

def recursive_add(s):
    if s:
        return s[0]**2 + recursive_add(s[1:])
    else:
        return 0

Upvotes: 6

DonCallisto
DonCallisto

Reputation: 29912

Your code does not what you want. In very first place, declare sum = 0 into recursive_add will lead to a different behaviour respect of that you expected.

I suggest to modify it in

def recursive_add(s,sum):
 if len(s) == 1:
  return sum + s[0] ** 2
 else:
  sum = s[0] ** 2 + recursive_add(s[1:],sum)
 return sum

And call it in that way

s = [8, 6, 8, 4]
print recursive_add(s,0)

Upvotes: 0

Related Questions