CODEWITHSUNDEEP
pythonrecursion
spamsyn
spamsyn

Reputation: 3

Output of function with 2 consecutive recursive statements

I am struggling to understand the output of a recursive function that calls itself twice. I understand that a function with this kind of structure is unlikely to ever be needed in practice, but as I'm new to programming, I thought it'd be helpful for me to understand the concept of recursion in a little more depth. I also have (I think) no trouble understanding the concept of recursion in a simpler case, i.e., factorial, Fibonacci seq.

I have run this through python tutor and attempted to use a debugger, but I'm afraid I still don't quite understand what is happening behind the scenes.

I have also searched this site, and although one or two people have asked similar questions, the answers given were not helpful for my case e.g. Calling recursive function twice consecutively

def recurse(n, s):
    if n == 0:
        print(s)
    else:
        recurse(n - 1, n + s)
        recurse(n - 1, n + 2*s)

recurse(2, 0)

This is what I thought was happening:

So the output I expect is 3, 5 but the output I get is 3, 5, 3, 5

Does the second recurse call then call the first? I had thought that 2 consecutive recursive statements executed independently, but that does not seem to be the case here.

Any help pointing out what exactly it is that I am not understanding would be very much appreciated.

Upvotes: 0

Views: 527

Answers (1)

Dipen Dadhaniya
Dipen Dadhaniya

Reputation: 4630

This is what happening:

  • recurse(2, 0)
    • 2 != 0, so pass along to else:
    • recurse(1, 2)
      • 1 != 0, so pass along to else:
      • recurse(0, 3)
        • 0 == 0, so print(3)
      • recurse(0, 5) // You missed recurse(n - 1, n + 2*s)
        • 0 == 0, so print(5)
    • recurse(1, 2)
      • 1 != 0, so pass along to else:
      • recurse(0, 3) // You missed recurse(n - 1, n + s)
        • 0 == 0, so print(3)
      • recurse(0, 5)
        • 0 == 0, so print(5)

Upvotes: 1

Related Questions