Need help in recursion

Question

I am trying to calculate the sum of 5 numbers in an array with recursion. However, I am getting the output as 0 from the recursive function. If I uncomment the print statement I am getting the sum as 15 but the function is returning the sum as 0. What am I doing wrong here??

My code-

def calcsum(arr):
  i = 0
  sum = 0
  solution(arr,sum,i)
  return sum

def solution(arr,sum,i):
  if i == len(arr):
    return

  sum = sum + arr[i]
  #print(sum,i)
  solution(arr,sum,i+1)

print(calcsum([1,2,3,4,5]))

Answer 1

Remember that recursion has at least two cases:

• Base case: return the aggregate value
• Recursive case: return the result of recursing

You're not returning a value from either case! Try this instead:

def solution(arr, sum_, i):
    if i == len(arr):
        return sum_

    sum_ += arr[i]
    return solution(arr, sum_, i+1)

Additionally, merely calling solution does not change the value of sum in calcsum, so return sum will always give 0. Try instead:

def calcsum(arr):
    return solution(arr, 0, 0)

(an aside, this sort of construction where you create a function which delegates the call to a helper with some added arguments reminds me a lot of Haskell, where you might write:

calcsum :: Num a => [a] -> a
calcsum = go 0 0
  where go :: Num a => Int -> Int -> [a] -> a
        go acc idx xs
            | length xs >= idx = acc
            | otherwise        = go (acc + (xs !! idx)) idx+1 xs

Also your logic is a little convoluted. Consider instead something like:

def solution(arr):
    if arr:
        # Recursive case
        x, rest = arr[0], arr[1:]
        return x + solution(rest)
    else:
        # Base case
        return 0

The base case now is when arr is empty (rather than when you've passed an index that's outside the array). You calculate the sum of the empty list which can only logically by 0. The recursive case pulls the first element off the list and adds it to the solution for the rest of the list.

Answer 2

As mentioned already, you should return the sum. Here's an iterator version:

def calcsum(arr):
    return solution(iter(arr), 0)

def solution(it, sum):
    for x in it:
        return solution(it, sum + x)
    return sum

print(calcsum([1,2,3,4,5]))

Shorter way using only one function and only one parameter, adding x after the recursion:

def calcsum(it):
    it = iter(it)
    for x in it:
        return x + calcsum(it)
    return 0

print(calcsum([1,2,3,4,5]))

Both solutions take linear time, unlike the similar solution that takes only arr and splits it into arr[0] and arr[1:], which takes overall quadratic time. A little benchmark comparing this iterator version with that list version by summing a list of 1000 values:

0.28 ms  calcsum_1
2.70 ms  calcsum_2

Benchmark code:

from timeit import repeat

def calcsum_1(it):
    it = iter(it)
    for x in it:
        return x + calcsum_1(it)
    return 0

def calcsum_2(arr):
    if arr:
        x, rest = arr[0], arr[1:]
        return x + calcsum_2(rest)
    return 0

arr = [1] * 1000

for _ in range(3):
    for f in calcsum_1, calcsum_2:
        t = min(repeat(lambda: f(arr), number=1000))
        print('%.2f ms ' % t, f.__name__)
    print()

Answer 3

You can make it work "your way", i.e., increase the sum variable in calcsum, if you put solution inside of it and increase the outer sum instead of having its own. No need to pass arr then, either.

def calcsum(arr):

  def solution(i):
    nonlocal sum
    if i == len(arr):
      return

    sum = sum + arr[i]
    solution(i+1)

  sum = 0
  solution(0)
  return sum

print(calcsum([1,2,3,4,5]))

Answer 4

There are at least five issues with your code:

• The call to solution(arr, sum, i) in calcsum does not modify calcsum's local variable sum, thus calcsum always returns 0;
• You wrote return instead of return sum in the end case for the recursion in solution, so solution will return None instead of returning the sum in that case
• You wrote the recursive call as solution(arr,sum,i+1) instead of return solution(arr,sum,i+1) or some_variable = solution(arr,sum,i+1), so the return value of the recursive call is ignored anyway; there is no return statement except the one inside the if block, so the function solution will not have a return value (or more precisely, it will return None);
• You seem to believe that modifying sum inside solution will modify any variable called sum throughout your program. This is wrong. sum is a local variable of the function, and modifying it has no impact on the rest of the program.
• Calling a variable sum is a bad idea in python; this is the name of a builtin function, so you should try to find another name for your variables.

To illustrate the fourth point, try out this code:

def mostly_harmless(n):
  n = 7

n = 8
mostly_harmless(n)
print('Does this set n to 7? Am I about to print 8 or 7?')
print(n)

print()

mostly_harmless(12)
print('did we set 12 = 7? did we just break all of mathematics?')
print('making sure 12 is still 12:')
print(12)
print('making sure n is still n:')
print(n)

With this in mind, we can fix your code:

def calcsum(arr):
  return solution(arr, 0, 0)

def solution(arr, sum, i):
  if i == len(arr):
    return sum
  else:
    return solution(arr, sum + arr[i], i+1)

print(calcsum([1,2,3,4,5]))

Actually, we can simplify the code further using default arguments:

def calcsum(arr, sum=0, i=0):
  if i == len(arr):
    return sum
  else:
    return calcsum(arr, sum + arr[i], i+1)

print(calcsum([1,2,3,4,5]))

But note that python is not a language that likes recursion. In some other programming languages, recursion is very good, and exactly as efficient as for loops and while loops. But that is not the case in python. In python, recursion is much slower than loops, and uses much more memory. We can rewrite your program with a for loop:

def calcsum(arr):
  sum = 0
  for i in range(len(arr)):
    sum += arr[i]
  return sum

print(calcsum([1,2,3,4,5]))

Or even better:

def calcsum(arr):
  sum = 0
  for v in arr:
    sum += v
  return sum

print(calcsum([1,2,3,4,5]))

Also note that calling a variable sum in python is a bad idea, because sum is the name of a builtin function in python. You can find a list of builtins in the python documentation; try to give other names to your variables.

The function sum, unsurprisingly, calculates the sum all by itself:

print(sum([1,2,3,4,5]))

So why was it so bad to call a variable sum? Well, then we lose access to the builtin function with the same name:

sum = 7
print(sum([1,2,3,4,5]))
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: 'int' object is not callable

Normally sum refers to the builtin function; but now it refers to a variable equal to 7; when I try to call sum([1,2,3,4,5]), it's as if I tried to call 7([1,2,3,4,5]), which doesn't make sense because 7 is not a function.