How two recursion function in program works?
<p>I am learning Recursion and understand single recursion like Factorial . I am facing problem to understand how two recursive function works ? I am trying to understand this code :</p>

<pre><code>def countdown(n,m):

    if n == 0:  # this is the base case
        return  # return, instead of making more recursive calls
    print("before recursion",n)

    countdown(n - 1,m)                    # first recursive call
    print("first recursion",n)       
    countdown(n - 1,m)
    print("Second recursion",n)            # second recursive call



countdown(3,4)
</code></pre>

<p>And the output is :</p>

<pre><code>before recursion 3
before recursion 2
before recursion 1
first recursion 1
Second recursion 1
first recursion 2
before recursion 1
first recursion 1
Second recursion 1
Second recursion 2
first recursion 3
before recursion 2
before recursion 1
first recursion 1
Second recursion 1
first recursion 2
before recursion 1
first recursion 1
Second recursion 1
Second recursion 2
Second recursion 3
</code></pre>

<p>I tried to understand with visual python :</p>

<p><a href="http://pythontutor.com/visualize.html#code=def%20countdown(n,m%29%3A%0A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%20%20%23%20this%20is%20the%20base%20case%0A%20%20%20%20%20%20%20%20return%20%20%23%20return,%20instead%20of%20making%20more%20recursive%20calls%0A%20%20%20%20print(%22before%20recursion%22,n%29%0A%0A%20%20%20%20countdown(n%20-%201,m%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20first%20recursive%20call%0A%20%20%20%20print(%22first%20recursion%22,n%29%20%20%20%20%20%20%20%0A%20%20%20%20countdown(n%20-%201,m%29%0A%20%20%20%20print(%22Second%20recursion%22,n%29%20%20%20%20%20%20%20%20%20%20%20%20%23%20second%20recursive%20call%0A%0A%0A%0Acountdown(3,4%29&amp;cumulative=false&amp;curInstr=0&amp;heapPrimitives=false&amp;mode=display&amp;origin=opt-frontend.js&amp;py=3&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false" rel="nofollow">Visualize Python code live</a></p>

<p>I am understanding first recursion process but when second recursion start , I am facing problem to understand behaviour of second recursion </p>

<p>Let me explain what i am not understanding :</p>

<p>Ok so this is situation where first recursion finish after finding this base condition (n==0)</p>

<p><a href="https://i.stack.imgur.com/9R6aV.png" rel="nofollow"><img src="https://i.stack.imgur.com/9R6aV.png" alt="First recursion found base condition"></a></p>

<p>Now here second recursion start work</p>

<p><a href="https://i.stack.imgur.com/U7oHo.png" rel="nofollow"><img src="https://i.stack.imgur.com/U7oHo.png" alt="enter image description here"></a></p>

<p>, My confusion is until i have learned "below part of recursion would not execute until recursion found its base condition so first recursion didn't print <code>"first recursion 1"</code> until it found base condition in this program , i understand this point clearly. But now when second recursion start working it print immediately <code>"Second recursion 1"</code>(<code>print("Second recursion",n)</code> ) without completing recursion ?? My main confusion is this.</p>

<p>If you are confuse please see step 36 to 43 here <a href="http://pythontutor.com/visualize.html#code=def%20countdown(n,m%29%3A%0A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%20%20%23%20this%20is%20the%20base%20case%0A%20%20%20%20%20%20%20%20return%20%20%23%20return,%20instead%20of%20making%20more%20recursive%20calls%0A%20%20%20%20print(%22before%20recursion%22,n%29%0A%0A%20%20%20%20countdown(n%20-%201,m%29%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20first%20recursive%20call%0A%20%20%20%20print(%22first%20recursion%22,n%29%20%20%20%20%20%20%20%0A%20%20%20%20countdown(n%20-%201,m%29%0A%20%20%20%20print(%22Second%20recursion%22,n%29%20%20%20%20%20%20%20%20%20%20%20%20%23%20second%20recursive%20call%0A%0A%0A%0Acountdown(3,4%29&amp;cumulative=false&amp;curInstr=0&amp;heapPrimitives=false&amp;mode=display&amp;origin=opt-frontend.js&amp;py=3&amp;rawInputLstJSON=%5B%5D&amp;textReferences=false" rel="nofollow">Visualize Python code live</a></p>

<p>If i understand this then i would be able to understand tower of hanoi problem. But i want to understand first how second recursion work in program.</p>

<p>You can visualize the sequence of calls and returns in a tree like this:</p>

<p><a href="https://i.stack.imgur.com/yLESp.jpg" rel="nofollow"><img src="https://i.stack.imgur.com/yLESp.jpg" alt="enter image description here"></a></p>

<p>The calls traverse this tree left to right, depth first:</p>

<p><a href="https://i.stack.imgur.com/piBm7.jpg" rel="nofollow"><img src="https://i.stack.imgur.com/piBm7.jpg" alt="enter image description here"></a></p>

<p>Hopes this helps your intuition a bit. 'Arrow down' is call, 'arrow up' is return. Each function call has it's own lump of data, called a 'stack frame'. That's were' your n is remembered FOR THAT CALL. With each call a new stack frame is created. With each return the stack frame of the function you return from is destroyed. If you're 3 calls deep, you'll have 3 stack frames, containing e.g. n == 3, n == 2, n == 1 respectively.</p>

<p>At the deepest point, look at the green arrows:</p>

<p><a href="https://i.stack.imgur.com/fTDRu.jpg" rel="nofollow"><img src="https://i.stack.imgur.com/fTDRu.jpg" alt="enter image description here"></a></p>

<p>Have added green arrows to illustrate the point where the first recursion terminates and the second begins. Since traversal is depth first it starts at the lowest point, not at the root / top</p>

python python-3.x recursion