Why recursive function is considering last element in an array twice?

Question

Trying to understand recursive functions and so created this program but the output is incorrect. Would like to understand what am I doing wrong here

class Recursive:
    
    def __init__(self, arr):
        self.arr = arr
        self.sum = 0
        
    def sumRecursive(self):
    
        if len(self.arr) == 0:
            return self.sum
        self.sum = self.arr.pop(0)
        return self.sum + self.sumRecursive()
    
def main():
    recur = Recursive([1,2,3])
    print(recur.sumRecursive())

main()

output: 9

When programmers design a recursive algorithm, what is the first consideration? — quamrana, May 25 '21 at 19:37
why is sum a member variable of the Recursive class? You probably want it to be a local variable of the sumRecursive function. The code there overwrites the sum variable in each call, leaving with a sum of 3 + 3 + 3 when the first call is resolved. — Zheoni, May 25 '21 at 19:39
Ok, that's the test for the base case. What code needs to be written for that base case? — quamrana, May 25 '21 at 19:43
Your function is not tail-recursive, but you are using an accumulator as if it were. — chepner, May 25 '21 at 19:47
Well, the base case says that you are considering an empty array, whose sum is `0`, so just return `0`. — quamrana, May 25 '21 at 19:49

score 2 · Answer 1 · answered May 25 '21 at 19:52

2

There are two types of recursion to consider: tail recursion, where the return value of a single recursive call is returned as-is, and "regular" recursion, where you do something with the return value(s) of the recursive call(s) before returning yourself.

You are combining the two. You either add a value from the list to the recursive sum, using no accumulator:

def non_tail_recursive(self):
    if len(self.arr) == 0:
        return 0
    return self.arr.pop(0) + self.non_tail_recursive()

or you use an accumulator:

def tail_recursive(self):
    if len(self.arr) == 0:
         return self.sum

    self.sum += self.arr.pop(0)
    return self.tail_recursive()

answered May 25 '21 at 19:52

chepner

497,756
71
530
681

Thank you so much for the explanation. Very helpful. – Nikhil Sahni May 25 '21 at 20:20
this is an [oversimplification](https://en.wikipedia.org/wiki/Category:Recursion_schemes) – Mulan May 26 '21 at 04:08
Recursion schemes are somewhat orthogonal to the distinction I'm drawing here. – chepner May 26 '21 at 12:39

score 1 · Answer 2 · answered May 25 '21 at 19:43

1

You don't usually use an object with state to implement recursion. If you're keeping state, then you often don't need a recursive solution at all.

Here's how to do a "stateless" recursive sum.

def sumRecursive(arr):
    if not arr:
        return 0
    return arr[0] + sumRecursive(arr[1:])

def main():
    print(sumRecursive([1,2,3]))

main()

answered May 25 '21 at 19:43

Tim Roberts

48,973
4
21
30

Thank you so much for the explanation. Very helpful. – Nikhil Sahni May 25 '21 at 20:20

score 1 · Answer 3 · answered May 25 '21 at 19:51

Your self.sum attribute is redundant. The information being processed by a recursive algorithm rarely needs members to pass information along.

class Recursive:
    
    def __init__(self, arr):
        self.arr = arr
        
    def sumRecursive(self):
    
        if not len(self.arr):
            return 0
        return self.arr.pop(0) + self.sumRecursive()
    
def main():
    recur = Recursive([1,2,3])
    print(recur.sumRecursive())

main()

Output: 6

thank you so much for explaining this. Much appreciated. – Nikhil Sahni May 25 '21 at 20:19 — Nikhil Sahni, May 25 '21 at 20:19

JNevill · Answer 4 · 2021-05-25T19:52:24.623

To answer your question without rewriting your code (since obviously there are better ways to sum arrays), the answer is that the last leg of your recursion calls self.sum + self.sumRecursive which hits your sumRecursive function one last time which returns (from your if statement) self.sum which is the last element in your list (which you already summed).

Instead when the array is empty, return 0.

class Recursive:

    def __init__(self, arr):
        self.arr = arr
        self.sum = 0
        
    def sumRecursive(self):

        if len(self.arr) == 0:
            return 0 
        self.sum = self.arr.pop(0) 
        return self.sum + self.sumRecursive()


    def main():
        recur = Recursive([1,2,3,4])
        print(recur.sumRecursive())

main()

Optionally move your if to the bottom where I personally think it makes more sense:

def sumRecursive(self):
    self.sum = self.arr.pop(0)  
    if len(self.arr) == 0:
        return self.sum
    else:      
        return self.sum + self.sumRecursive()

Mulan · Answer 5 · 2021-05-26T05:32:06.963

fundamentals

You are making this more challenging for yourself because you are tangling your sum function with the class. The sum function simply needs to work on a list but the context of your object, self, is making it hard for you to focus.

Recursion is a functional heritage and this means writing your code in a functional and modular way. It's easier to read/write small, single-purpose functions and it promotes reuse within other areas of your program. Next time you need to sum a list in another class, do you want to rewrite sumRecursive again?

Write your summing function once and then import it where it's needed -

# mymath.py

def mysum(t):
  if not t:
    return 0
  else:
    return t.pop() + mysum(t)

See how mysum has no concern for context, self? Why should it? All it does it sum the elements of a list.

Now write your recursive module -

# recursive.py

from mymath import mysum

class Recursive:
  def __init__(self, arr): self.arr = arr
  def sum(self): return mysum(self.arr)

See how Recursive.sum just hands off self.arr to mysum? It doesn't have to be more complicated than that. mysum will work on every list, not just lists within your Recursive module. We don't have to know how mysum works, that is the concern of the mymath module.

Now we write the main module. Each module represents a barrier of abstraction. This means that the details of a module shouldn't spill over into other modules. We don't know how Recursive actually sums the input, and from the caller's point of view, we don't care. That is the concern of Recursive module.

# main.py

from recursive import Recursive

recur = Recursive([1,2,3])
print(recur.sum())

going functional

Above we wrote mysum using the .pop technique in your question. I did this because that seems to be how you are understanding the problem right now. But watch what happens when we do this -

x = [1,2,3]
print(mysum(x)) # 6
print(mysum(x)) # 0

Why does the mysum return a different answer the second time? Because as it is written now, mysum uses t.pop(), which mutates t. When mysum is finished running, t is completely emptied!

By why would we write our function like this? What if 5 + x returned a different result each time we called it?

x = 3
print(5 + x) # 8
print(5 + x) # 8

How annoying it would be if we could not depend on values not to change. The sum of the input, [1,2,3], is 6. But as it is written, the sum of the input is to return 6 and empty the input. This second part of emptying (changing) the input is known as a side effect. Ie, the desired effect is to sum and emptying of the input list is unintended but a consequence of us using .pop to calculate the result. This is not the functional way. Functional style means avoiding mutations, variable reassignments, and other side effects.

def mysum(t):
  if not t:
    return 0
  else:
    return t[0] + mysum(t[1:])

When written in this way, t, is not changed. This allows us to use equational reasoning whereby we can substitute any function call for its return value and always get the correct answer

x = [1,2,3]
mysum(x)
== 1 + mysum([2,3])
== 1 + 2 + mysum([3])
== 1 + 2 + 3 + mysum([])
== 1 + 2 + 3 + 0
== 1 + 2 + 3
== 1 + 5
== 6

And x was not changed as a result of running mysum -

print(x)
# [1,2,3]

Note, the Recursive module does not need to make any change to receive the benefit of rewriting mysum in this way. Before the change, we would've seen this behavior -

# main.py

from recursive import Recursive

recur = Recursive([1,2,3])
print(recur.sum())
print(recur.sum())

6
0

Because the first call to sum passes self.arr to mysum which empties self.arr as a side effect. A second call to recur.sum() will sum an empty self.arr! After fixing mysum we get the intended behaviour -

# main.py

from recursive import Recursive

recur = Recursive([1,2,3])
print(recur.sum())
print(recur.sum())

6
6

additional reading

I've written extensively about the techniques used in this answer. Follow the links to see them used in other contexts with additional explanation provided -

Why recursive function is considering last element in an array twice?

5 Answers5