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...
In recursion, a function or method has the ability to call itself to solve the problem. The process of recursion involves solving a problem by turning it into smaller varieties of itself. The process in which a function calls itself could happen directly as well as indirectly.
Recursion is the process which comes into existence when a function calls a copy of itself to work on a smaller problem. Any function which calls itself is called recursive function, and such function calls are called recursive calls. Recursion involves several numbers of recursive calls.
Recursion is the process in which a function calls itself up to n-number of times. If a program allows the user to call a function inside the same function recursively, the procedure is called a recursive call of the function. Furthermore, a recursive function can call itself directly or indirectly in the same program.
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...
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.
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):
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With