[ACCEPTED]-How Recursion works in C-recursion

Lets assume a function:

int MyFunc(int counter) {
    // check this functions counter value from the stack (most recent push)

    // if counter is 0, we've reached the terminating condition, return it
    if(counter == 0) {
        return counter;
    }
    else {
        // terminating condition not reached, push (counter-1) onto stack and recurse
        int valueToPrint = MyFunc(counter - 1);

        // print out the value returned by the recursive call 
        printf("%d", valueToPrint);

        // return the value that was supplied to use 
        // (usually done via a register I think)
        return counter;
    }
}

int main() {
    // Push 9 onto the stack, we don't care about the return value...
    MyFunc(9);
}

The output is: 012345678

The 18 first time through MyFunc, count is 9. It fails 17 the terminating check (it is not 0), so 16 the recursive call is invoked, with (counter -1), 8.

This 15 repeats, decrementing the value pushed onto 14 the stack each time until counter == 0. At this point, the 13 terminating clause fires and the function 12 simply returns the value of counter (0), usually 11 in a register.

The next call up the stack, uses 10 the returned value to print (0), then returns 9 the value that was supplied into it when 8 it was called (1). This repeats:

The next 7 call up the stack, uses the returned value 6 to print (1), then returns the value that 5 was supplied into it when it was called 4 (2). etc, till you get to the top of the 3 stack.

So, if MyFunc was invoked with 3, you'd 2 get the equivalent of (ignoring return addresses 1 etc from the stack):

Call MyFunc(3) Stack: [3]
Call MyFunc(2) Stack: [2,3]
Call MyFunc(1) Stack: [1,2,3]
Call MyFunc(0) Stack: [0,1,2,3]
Termination fires (top of stack == 0), return top of stack(0).
// Flow returns to:
MyFunc(1) Stack: [1,2,3]
Print returned value (0)
return current top of stack (1)

// Flow returns to:
MyFunc(2) Stack: [2,3]
Print returned value (1)
return current top of stack (2)

// Flow returns to:
MyFunc(3) Stack: [3]
Print returned value (2)
return current top of stack (3)

// and you're done...

How things get unwind when the exit condition is reached?

First, few words about recursion: a divide and conquer method used 41 for complex tasks that can be gradually 40 decomposed and reduced to a simple instances 39 of the initial task until a form^{(base case)} that allows 38 direct calculation is reached. It is a notion 37 closely related to mathematical induction.

More specifically, a 36 recursive function calls itself, either directly or indirectly. In 35 direct recursion function, foo(), makes another 34 call to itself. In indirect recursion, function 33 foo() makes a call to function moo(), which in turn 32 calls function foo(), until the base case is 31 reached, and then, the final result is accumulated 30 in the exact reverse order of the initial 29 recursive function call.

Example:

Factorial n, denoted 28 n!, is the product of positive integers from 27 1 to n. The factorial can be formally defined 26 as:
factorial(0)=1, (base case)
factorial(n)= n * factorial(n-1), for n > 0. (recursive call)

Recursion shows up in 25 this definition as we define factrorial(n) in terms of 24 factorial(n-1).

Every recursion function should have termination condition to 23 end recursion. In this example, when n=0, recursion 22 stops. The above function expressed in C is:

int fact(int n){
    if(n == 0){ 
        return 1;
    }
    return (n * fact(n-1));
}

This 21 example is an example of direct recursion.

How is this implemented? At 20 the software level, its implementation is 19 not different from implementing other functions(procedures). Once 18 you understand that each procedure call instance is distinct from 17 the others, the fact that a recursive function 16 calls itself does not make any big difference.

Each 15 active procedure maintains an activation record, which is 14 stored on the stack. The activation record 13 consists of the arguments, return address (of the caller), and local variables.

The activation 12 record comes into existence when a procedure 11 is invoked and disappears after the procedure 10 is terminated and the result is returned 9 to the caller. Thus, for each procedure that is not terminated, an activation record that contains the state of that procedure is stored. The number of activation 8 records, and hence the amount of stack space 7 required to run the program, depends on 6 the depth of recursion.

Also can anyone please give me a diagramatic view of recursion?

Next figure shows 5 the activation record for factorial(3):

As you can see from the figure, each call 4 to the factorial creates an activation record 3 until the base case is reached and starting 2 from there we accumulate the result in the 1 form of product.

In C recursion is just like ordinary function 4 calls.

1. When a function is called, the arguments, return address, and frame pointer (I forgot the order) are pushed on the stack.
2. In the called function, first the space for local variables is "pushed" on the stack.
3. if function returns something, put it in a certain register (depends on architecture, AFAIK)
4. undo step 2.
5. undo step 1.

So, with recursion steps 1 and 2 3 are performed a few times, then possibly 2 3 (maybe only once) and finally 4 and 5 1 are done (as many times as 1 and 2).

An alternative answer is that in general 9 you don't know. C as a language doesn't 8 have any stack of heap. Your compiler uses 7 a memory location called the stack to store 6 control flow information such as stack frames, return 5 addresses and registers, but there is nothing 4 in C prohibiting the compiler to store that 3 information elsewhere. For practical aspects 2 the previous answers are correct. This is 1 how C compilers operate today.

This question has been widely answered. Allow 40 me please to incorporate an additional answer 39 using a more pedagogical approach.

You can 38 think function recursion as a stack of bubbles with 37 two differentiate stages: pushing stage 36 and bursting stage.

A) PUSHING STAGE (or "Pushing the stack", as OP call it)

0) The starting Bubble #0 is the 35 MAIN function. It is blown up with this 34 information:

• Local variables.
• The call to the next Bubble #1 (the first call to the recursive function, MYFUNC).

1) Bubble #1 is blown up on its turn 33 with this information:

• Parameters from the previous Bubble #0.
• Local variables if necessary.
• A returning address.
• Terminating check with a returning value (eg: if (counter == 0) {return 1}).
• A call to the next Bubble #2.

Remember that this 32 bubble, as the other bubbles, is the recursive 31 function MYFUNC.

2) Bubble #2 is blown up with the 30 same information as Bubble #1, getting from 29 the latter the necessary input (parameters). After 28 this point, you can stack as many bubbles 27 as you want inflating the information accordingly 26 to the listed items in Bubble #1.

i) So you 25 get as many bubbles as you want: Bubble 24 #3, Bubble #4..., Bubble #i. The very last bubble 23 has a NAIL in the terminating check. Be 22 aware!

B) BURSTING STAGE (or "Popping the stack", as OP call it)

This stage happens when you reach 21 the positive terminating check and the last 20 bubble containing the nail is burst.

Let's 19 say this stage happens in Bubble #3. The 18 positive terminating check is reached and 17 Bubble #3 is burst. Then the NAIL from this 16 bubble is liberated. This nail falls on 15 the underneath Bubble #2 and burst it. After 14 this happens the nail follows its fall until 13 it burst Bubble #1. The same happens to 12 Bubble #0. It is important to notice that 11 the nail follows the returning address in 10 the bubble that it's being burst at the 9 moment: the address tells the nail which 8 direction to follow while falling.

At the 7 end of this process, the answer is obtained 6 and delivered to the MAIN function (or Bubble 5 #0, which of course is not burst).

C) GRAPHICALLY (as OP asked)

This is 4 the graphical explanation. It evolves from 3 the bottom, Bubble #0 to top, Bubble #3.

/*Bubble #3 (MYFUNC recursive function): Parameters from Bubble #2,
local variables, returning address, terminating check (NAIL),
call (not used here, as terminating check is positive).*/

Pushing up to the bubble above ↑ ----------------------------------------------------- 🡓 Nail falls to Bubble #2

/*Bubble #2 (MYFUNC recursive function): Parameters from Bubble #1,
local variables, returning address, terminating check (not used),
call to Bubble #3.*/

Pushing up to the bubble above ↑ ----------------------------------------------------- 🡓 Nail falls to Bubble #1

/*Bubble #1 (MYFUNC recursive function): Parameters from Bubble #0,
local variables, returning address, terminating check (not used),
call to Bubble #2.*/

Pushing up to the bubble above ↑ ----------------------------------------------------- 🡓 Nail falls to Bubble #0

/*Bubble #0 (MAIN function): local variables, the first call to Bubble #1.*/

Hope 2 this approach helps someone. Let me know 1 if any clarification is needed.