Baap Baap - 1 month ago 9
Python Question

What happen after recursion found base condition?

I am trying to understand recursion , I am following stackoverflow answer Understanding recursion but i am not getting what i am looking. until i have learned this :

" if recursion is in program then below block of code will not execute until recursion found its base condition, once it found its base condition then that recursion will never execute again and now below block of code will execute without recursion "
is am getting right ?

Here is a program :

def countdown(n):
print(n)

if n == 0:
return

countdown(n - 1) # the recursive call

countdown(4)


I tried to take help of python visualized code , so my confusion is first recursive function will call function again and again until it found base condition ,ok i understand this part ,like in this program it found base condtion if
n==0
so now n is 0 and return value is 0 , i understand this :

enter image description here

but what happen after ? why it return result in reverse order after found base condition ? this is my confusion , why its going reverse ? its like first its unpacking values then its packing old values ? from where n=1 came ?? how ??

enter image description here

now n=2 how ? how its going reverse ???? whats happening here ?

enter image description here

now n=3 then n=4 and then at last it goes to first where it started , whats happening here , my big confusion is what happen after base condition found

like in 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)


when it found base condition that if list is empty return result so after it found base condition why its printing result it reverse ?

enter image description here

Answer

What you have is simply a call stack. Whenever a function calls another function, that new call is pushed onto the call stack.

def a():
    b()

def b():
    c()

def c():
    pass

a()

a calls b, b calls c. You now have a call stack of abc. Once c returns, the stack will be unwound in the reverse order: c will get discarded from the top, then b, finally a.

This is more apparent when there's something after the function call:

def a():
    b()
    print('foo')

def b():
    pass

a()

a will get executed and call b. Now you have a call stack of ab. b finishes, popping off the stack. You now have a call stack of just a. Then 'foo' will be output. Then the stack unwinds completely.

This is no different with a recursive function, only that instead of three different functions, you're calling the same function. You'll have a call stack of countdowncountdowncountdown → …, or countdown(4)countdown(3)countdown(2) → …

BTW, the call stack is what you see as stack trace whenever you see Python's default error output:

Traceback (most recent call last):
  File …, line …, in <module>
  File …, line …, in a
  File …, line …, in b
  File …, line …, in c
SomeError: some message

It tells you what functions where called in what order to get to the place the error occurred.