Two similar recursion codes

Question

I am preparing for interviews but Recursion baffles me. I am confused by the o/p of the two similar codes

def fun(x):
   if(x > 0):
        x -= 1
        fun(x) 
        print(x , end=" ")
        x -= 1
        fun(x) 
   
# Driver code
a = 4
fun(a) 

output=0 1 2 0 3 0 1

I am confused like why in above code 4 and the intermediate values are not pushed on to the stack just like in below code.

def fun(x):
   if(x > 0):
        fun(x-1) 
        print(x , end=" ")
        x -= 1
        fun(x) 
   
# Driver code
a = 4
fun(a) 

output=1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Usually with code like this I like to execute it in my head and write it out on paper. It really helps with understanding how exactly some code works. That, or stepping through in a GUI debugger. — Random Davis, Jan 22 '21 at 16:11
Try adding a "fun invoked with x=" print to the start of the function. Maybe that will help you understand it better. — , Jan 22 '21 at 16:12
If you are using an IDE **now** is a good time to learn its debugging features Or the built-in [Python debugger](https://docs.python.org/3/library/pdb.html). Printing *stuff* at strategic points in your program can help you trace what is or isn't happening. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — wwii, Jan 22 '21 at 16:14
Pay attention to the statement `x -= 1` that does something different than just calling `f(x-1)` — Zois Tasoulas, Jan 22 '21 at 16:19
Also, the clear difference between the two is that the second piece of code is subtracting `x` once, but the first piece of code subtracts it twice. So, the second piece of code will print more since it'll take `x` longer to reach 0. `fun(x-1)` does not affect `x`, but `x -= 1` does. — Random Davis, Jan 22 '21 at 16:20
I debugged it but my question is related to the memory allocation in Recursion. In first code when we are calling function with 4 why 4 wasn't pushed on to stack, as it happened in the 2nd code.When stack unravels, after the last call, 4 wasn't printed for the first code but it got printed in the 2nd one. — Micky, Jan 22 '21 at 16:23
@RandomDavis also why in first code 0 is getting printed .In the loop, the condition is x>0, then how it is getting printed — Micky, Jan 22 '21 at 16:29
@Micky because if `x = 1`, then it gets subtracted once before being printed. It can pass the `x > 0` condition because it's `1`, then it gets subtracted once, then printed. — Random Davis, Jan 22 '21 at 16:33
@RandomDavis but its getting deducted before fun(x) call. So in the end fun(0) will get called. Actually it is printing 0 from the stack once first recursive call is over. Please see my debug image above. I have marked the o/p with yellow color. — Micky, Jan 22 '21 at 16:48
@Micky if `x = 1`, then it'll pass the `if(x > 0)` check, then `x` will be set to `0`, and then `fun(0)` will run, which will produce no output. Then, execution will resume to the point where `fun(0)` was called, and the print statement after will execute, as well as the rest of the code. Calling `fun(0)` doesn't cause execution in the calling function to stop. It just continues on, just like any other code. Does that make sense? The only way calling `fun(0)` would end execution in the calling function is if you had a `return` statement, like `return fun(0)`. — Random Davis, Jan 22 '21 at 16:58

score 1 · Accepted Answer · answered Jan 22 '21 at 17:12

I modified your code to show the exact execution path so you can see why the output is happening.

Modified version of the first code:

def fun(x, depth=0):
   print(" " * depth + f"in fun({x}) (depth {depth})")
   print(" " * depth + f"if({x} > 0): (depth {depth})")
   if(x > 0):
        print(" " * depth + f"x = {x} - 1 = {x - 1} (depth {depth})")
        x -= 1
        print(" " * depth + f"calling fun({x}) (depth {depth})")
        fun(x, depth + 1)
        print(" " * depth + f"\"{x} \" printed (depth {depth})************")
        print(" " * depth + f"x = {x} - 1 = {x - 1} (depth {depth})")
        x -= 1
        print(" " * depth + f"calling fun({x}) (depth {depth})")
        fun(x, depth + 1)
   
# Driver code
a = 4
fun(a)

Output:

in fun(4) (depth 0)
if(4 > 0): (depth 0)
x = 4 - 1 = 3 (depth 0)
calling fun(3) (depth 0)
 in fun(3) (depth 1)
 if(3 > 0): (depth 1)
 x = 3 - 1 = 2 (depth 1)
 calling fun(2) (depth 1)
  in fun(2) (depth 2)
  if(2 > 0): (depth 2)
  x = 2 - 1 = 1 (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "0 " printed (depth 3)************
   x = 0 - 1 = -1 (depth 3)
   calling fun(-1) (depth 3)
    in fun(-1) (depth 4)
    if(-1 > 0): (depth 4)
  "1 " printed (depth 2)************
  x = 1 - 1 = 0 (depth 2)
  calling fun(0) (depth 2)
   in fun(0) (depth 3)
   if(0 > 0): (depth 3)
 "2 " printed (depth 1)************
 x = 2 - 1 = 1 (depth 1)
 calling fun(1) (depth 1)
  in fun(1) (depth 2)
  if(1 > 0): (depth 2)
  x = 1 - 1 = 0 (depth 2)
  calling fun(0) (depth 2)
in fun(0) (depth 3)
   if(0 > 0): (depth 3)
  "0 " printed (depth 2)************
  x = 0 - 1 = -1 (depth 2)
  calling fun(-1) (depth 2)
   in fun(-1) (depth 3)
   if(-1 > 0): (depth 3)
"3 " printed (depth 0)************
x = 3 - 1 = 2 (depth 0)
calling fun(2) (depth 0)
 in fun(2) (depth 1)
 if(2 > 0): (depth 1)
 x = 2 - 1 = 1 (depth 1)
 calling fun(1) (depth 1)
  in fun(1) (depth 2)
  if(1 > 0): (depth 2)
  x = 1 - 1 = 0 (depth 2)
  calling fun(0) (depth 2)
   in fun(0) (depth 3)
   if(0 > 0): (depth 3)
  "0 " printed (depth 2)************
  x = 0 - 1 = -1 (depth 2)
  calling fun(-1) (depth 2)
   in fun(-1) (depth 3)
   if(-1 > 0): (depth 3)
 "1 " printed (depth 1)************
 x = 1 - 1 = 0 (depth 1)
 calling fun(0) (depth 1)
  in fun(0) (depth 2)
  if(0 > 0): (depth 2)

Modified version of the second code:

def fun(x, depth=0):
   print(" " * depth + f"in fun({x}) (depth {depth})")
   print(" " * depth + f"if({x} > 0): (depth {depth})")
   if(x > 0):
        print(" " * depth + f"calling fun({x-1}) (depth {depth})")
        fun(x-1, depth + 1)
        print(" " * depth + f"\"{x} \" printed (depth {depth})************")
        print(" " * depth + f"x = {x} - 1 = {x - 1} (depth {depth})")
        x -= 1
        print(" " * depth + f"calling fun({x}) (depth {depth})")
        fun(x, depth + 1)
   
# Driver code
a = 4
fun(a)

Output:

in fun(4) (depth 0)
if(4 > 0): (depth 0)
calling fun(3) (depth 0)
 in fun(3) (depth 1)
 if(3 > 0): (depth 1)
 calling fun(2) (depth 1)
in fun(2) (depth 2)
  if(2 > 0): (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
  "2 " printed (depth 2)************
  x = 2 - 1 = 1 (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
 "3 " printed (depth 1)************
 x = 3 - 1 = 2 (depth 1)
 calling fun(2) (depth 1)
  in fun(2) (depth 2)
  if(2 > 0): (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
  "2 " printed (depth 2)************
  x = 2 - 1 = 1 (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
"4 " printed (depth 0)************
x = 4 - 1 = 3 (depth 0)
calling fun(3) (depth 0)
 in fun(3) (depth 1)
 if(3 > 0): (depth 1)
 calling fun(2) (depth 1)
  in fun(2) (depth 2)
  if(2 > 0): (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
  "2 " printed (depth 2)************
  x = 2 - 1 = 1 (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
 "3 " printed (depth 1)************
 x = 3 - 1 = 2 (depth 1)
 calling fun(2) (depth 1)
  in fun(2) (depth 2)
  if(2 > 0): (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
  "2 " printed (depth 2)************
  x = 2 - 1 = 1 (depth 2)
  calling fun(1) (depth 2)
   in fun(1) (depth 3)
   if(1 > 0): (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)
   "1 " printed (depth 3)************
   x = 1 - 1 = 0 (depth 3)
   calling fun(0) (depth 3)
    in fun(0) (depth 4)
    if(0 > 0): (depth 4)

Two similar recursion codes

1 Answers1