17

I am new to C and I'm reading about recursion, but I am totally confused.

The main part where I'm getting confused is how things get unwind when the exit condition is reached. I would like to know how during recursion values got pushed and popped from stack.

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

Thanks...

5
  • 2
    Understanding how things work... science, engineering, systems... all requires a sort of doublethink. You have pretend you only know about some small piece of the problem in some idealized context. Very powerful means of focus. Recursion is kind-of the ultimate form of that. Just look at the inside of the proc, and forget about the outside. Each bit does what it's told, and in the aggregate something useful happens. Commented Apr 12, 2011 at 6:57
  • Are you confused about how recursion works in general, or about what is happening on an assembly code level when recursion occurs in c? Do you mean a diagram view of the stack?
    – shelman
    Commented Apr 12, 2011 at 7:04
  • a recursive call isn't actually different than calling some other routine. Commented Apr 12, 2011 at 7:07
  • Do you understand how a stack works? Basically each time the function calls itself, it adds to the stack. When the function returns it pops off the stack. Commented Apr 12, 2011 at 7:12
  • To be honest am confused about how recursion works in general,but its more confusing when i try to understand how things unwind when base conditon reaches . Actully i wanna to know when in recurssion first function call happen then how values pushed on stack and when base condtion reaches how its poped out.......and how return statement works in there??? Commented Apr 12, 2011 at 7:12

5 Answers 5

22

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 first time through MyFunc, count is 9. It fails the terminating check (it is not 0), so the recursive call is invoked, with (counter -1), 8.

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

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

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

So, if MyFunc was invoked with 3, you'd get the equivalent of (ignoring return addresses 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...
2
  • @Thanks Forsvarir for ur explainantion ... One thing i would like to know is with only one return statement whole stack is get poped out??? Commented Apr 12, 2011 at 7:19
  • @AMIT: The return statement returns from the currently executing instance of the function... then the previous instance continues it's execution until it reaches the return statement
    – forsvarir
    Commented Apr 12, 2011 at 7:27
11

How things get unwind when the exit condition is reached?

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

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

Example:

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

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

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

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

This example is an example of direct recursion.

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

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

The activation record comes into existence when a procedure is invoked and disappears after the procedure is terminated and the result is returned 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 records, and hence the amount of stack space required to run the program, depends on the depth of recursion.

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

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

enter image description here

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


5

In C recursion is just like ordinary function 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 are performed a few times, then possibly 3 (maybe only once) and finally 4 and 5 are done (as many times as 1 and 2).

3
  • 3's either going to not be be performed (function doesn't return a value) or as often as 1/2 etc... If you go into a recusive function and it returns something, it's going to do it every time
    – forsvarir
    Commented Apr 12, 2011 at 7:16
  • @forsvarir: right, if the function is not tail recursive, then 3 will be done more than once. If it is tail-recursive, then compilers can produce code where it happens only once.
    – subsub
    Commented Apr 12, 2011 at 7:28
  • gotcha :) No point loading the register value if you know it already contains the value you'd be putting there.
    – forsvarir
    Commented Apr 12, 2011 at 7:40
3

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

1
1

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

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


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

0) The starting Bubble #0 is the MAIN function. It is blown up with this 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 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 bubble, as the other bubbles, is the recursive function MYFUNC.

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

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

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

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

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

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


C) GRAPHICALLY (as OP asked)

This is the graphical explanation. It evolves from 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 this approach helps someone. Let me know if any clarification is needed.

Not the answer you're looking for? Browse other questions tagged or ask your own question.