#include <iostream>
using namespace std;

 void fun(int n){
    if(n <= 0) // step (A)
        return;

    fun(n-1); // Step(B)
    cout << n <<' '; // step (C) it is called backtrack
    return;
}
int main()
{
    fun(5);

    /*
     Note before we start
     step B is Recursion

     so Step C it's called a backtrack
     because step C will start after the Recursion end

     the function we start at 5 and go at 4 then 3 then 2 then 1 then 0

     and then it will back, when it back step C will start
     so the output will be 1 2 3 4 5 not 5 4 3 2 1

     so in recursion we start at 5 an go at 1
     and when we back the step C start

    */

    /*
        Recursion is Stack
        so to understand the Recursion we must make a stack

        |      |
        |      |
        |      |  stack :)
        |      |
        |      |
        |      |
        --------

        in Main Function we Call fun(5) so put it in stack;
        |      |
        |      |
        |      |
        |      |
        |      |
        |fun(5)| <- top
        --------

    inside the function
     void fun(int n){
        if(n <= 0) // step (A)
            return;

        fun(n-1); // Step(B)
        cout << n <<' '; // step (C)
        return;
    }
    we will start t step A , there is a condition

        if(n <= 0)
            return;

         5 <= 0  is false so he won't return ( think about "return" as "pop from stack" )
         it will continue  and go in step B
         and call fun(n-1) => fun(4) so put it in stack

        |      |
        |      |
        |      |
        |      |
        |fun(4)| <- top
        |fun(5)|
        --------
        we will repeat the function and go in step A again

        if(n <= 0)
            return;

         4 <= 0  is false so he won't return ( don't pop )
         it will continue  and go in step B
         and call fun(n-1) => fun(3) so put it in stack

        |      |
        |      |
        |      |
        |fun(3)| <- top
        |fun(4)|
        |fun(5)|
        --------
        we will repeat the function again and go in step A

        if(n <= 0)
            return;

         3 <= 0  is false
         continue and go in step B
         and call fun(n-1) => fun(2) so put it

        |      |
        |      |
        |fun(2)| <- top
        |fun(3)|
        |fun(4)|
        |fun(5)|
        --------
        we will repeat the function again and go in step A

        if(n <= 0)
            return;

         2 <= 0  is false
         continue and go in step B
         and call fun(n-1) => fun(1) so put it

        |      |
        |fun(1)| <- top
        |fun(2)|
        |fun(3)|
        |fun(4)|
        |fun(5)|
        --------
        we will repeat the function again and go in step A

        if(n <= 0)
            return;

         1 <= 0  is false
         continue and go in step B
         and call fun(n-1) => fun(0) so put it

        |fun(0)| <- top
        |fun(1)|
        |fun(2)|
        |fun(3)|
        |fun(4)|
        |fun(5)|
        --------
        now Repeat again and go in step A
        if(n <= 0)
            return;

         0 <= 0  is True So it will return ( That means that we will POP from stack )

        |      |
        |fun(1)| <- top
        |fun(2)|
        |fun(3)|
        |fun(4)|
        |fun(5)|
        --------

        ** next the Backtracking will be happened **

        remember in fun(1) we finish step (B) already
        so step (C) will start and print 1

        fun(n-1); // Step(B)
        cout << n <<' '; // step (C)
        return;

        after step step C
        there is a (return) that mean pop from stack

        |      |
        |      |
        |fun(2)| <- top
        |fun(3)|
        |fun(4)|
        |fun(5)|
        --------

        in fun(2) we finish step (B) already
        so step (C) will start and print 2

        after step step C
        there is a (return) that mean pop from stack

        |      |
        |      |
        |      |
        |fun(3)| <- top
        |fun(4)|
        |fun(5)|
        --------

        in fun(3) we finish step (B) already
        so step (C) will start and print 3

        after step step C
        there is a (return) that mean pop from stack

        |      |
        |      |
        |      |
        |      |
        |fun(4)| <- top
        |fun(5)|
        --------

        in fun(4) we finish step (B) already
        so step (C) will start and print 4

        after step step C
        there is a (return) that mean pop from stack

        |      |
        |      |
        |      |
        |      |
        |      |
        |fun(5)| <- top
        --------

        in fun(5) we finish step (B) already
        so step (C) will start and print 5

        after step step C
        there is a (return) that mean pop from stack

        |      |
        |      |
        |      |
        |      |
        |      |
        |      |
        --------

        Stack is Empty So The Function had been finished :D

        output : 1 2 3 4 5

    */

    return 0;
}