Baap Baap - 1 month ago 18
Python Question

why stack printing result in reverse order?

I am trying to understand this program :

def listSum(arr, result):
if not data:
return result

print("print final", listSum(arr[1:], result + arr[0]))
print("print A:", arr[1:])
print("print B:", result + arr[0])

listSum([1, 3, 4, 5, 6], 0)


Its printing result in reverse order :

print final 19
print A: []
print B: 19
print final None
print A: [6]
print B: 13
print final None
print A: [5, 6]
print B: 8
print final None
print A: [4, 5, 6]
print B: 4
print final None
print A: [3, 4, 5, 6]
print B: 1


Please make me understand what is going on here? If this happening causes of recursion please make me understand how and why ? Explain in depth please

Answer

Sorry i seen your message too late,I just seen three question about recursion which you asked , I think you are confuse because you don't know the fundamental of recursion , How recursion works.

For understanding recursion ---> you have to understand how stack works , how stack store function and values of program.

I recommend you read this article which explain from scratch how stack store values and return values in terms of recursion. If want more info about recursion i suggest read first 100 page of SICP book

Its not printing result in reverse order its returning values from the stack.

You have to understand two things :

  • Stack works on Last In first Out principal , So Stack return values which comes last.

enter image description here

  • There are two types of recursion :
    • Head Recursion
    • Tail Recursion

In Head recursion recursive call first find its base condition then execute rest of code.

def head_recursion(x):
    if x==0:
        return
    else:
        head_recursion(x-1)
        print("Head Recursion",x)

head_recursion(3)

it will print :

Head Recursion 1
Head Recursion 2
Head Recursion 3

In tail recursion , Everything execute first after recursion call main function. It means In tail recursion Recursive call is last thing in function.

def head_recursion(x):
    if x==0:
        return
    else:
        print("Head Recursion",x)
        head_recursion(x-1)


head_recursion(3)

it will print :

Head Recursion 3
Head Recursion 2
Head Recursion 1

In your code its Head Recursion because after recursive call there is print and other code in function , so recursive call is not last thing in function.

As i said above in Head recursion , Recursive call first find its base condition then execute rest of code below of recursive call , Until it keep executing. So as it found base condition two things happen :

It print rest of code below of recursive function.
It start returning values from stack.

It will print final value when all the work will be done and recursive call will find its base condition. That's why final value 19 executed at last and returned at first (causes of LIFO).

The Stack When you call a function the arguments to that function plus some other overhead is put on the stack. Some info (such as where to go on return) is also stored there. When you declare a variable inside your function, that variable is also allocated on the stack.

Deallocating the stack is pretty simple because you always deallocate in the reverse order in which you allocate. Stack stuff is added as you enter functions, the corresponding data is removed as you exit them. This means that you tend to stay within a small region of the stack unless you call lots of functions that call lots of other functions (or create a recursive solution).that's why it seems reverse to you.