How do recursive functions work?

To understand how recursion works, we need to look at the behaviour of the run time stack as we make the function calls.

The runtime stack is a structure that keeps track of function calls and local variables as the program runs. When a program begins, the main() function is placed on the run time stack along with all variables local to main(). Each time a function is called, it gets added to the top of the runtime stack along with variables and parameters local to that function. Variables below it become inaccessible. When a function returns, the function along with it's local variables are popped off the stack allowing access to its caller and its callers variables.

Suppose we have the following program:

unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;              //base case result
    if(n > 1)                 //if n > 1 we  have the recursive case
        rc= n * factorial(n-1);  //rc is n * (n-1)!
    }
    return rc;
}
int main(void){
    unsigned int x = factorial(4);
    return 0;
}

Lets trace what happens to it with respect to the run time stack:

Program begins, main() function is placed on stack along with local variable x.

factorial(4) is called, so we push factorial(4) onto the stack along with local variables n and rc.

n is 4, and thus the if statement in line 3 is true, thus we need to call factorial(3) to complete line 4.

Note that in each function call to factorial on stack there is a value for n and rc. Each n and rc are separate variables so changing it in one function call on stack will have no effect on values held in other factorial function calls on stack.

PreviousWriting a recursive function NextAnalysis of a Recursive Function

Last updated 6 years ago

unsigned int factorial(unsigned int n){ unsigned int rc = 1 ; //base case result if(n > 1) //if n > 1 we have the recursive case rc= n * factorial(n-1); //rc is n * (n-1)! } return rc; } int main(void){ unsigned int x = factorial(4); return 0; }