Home > Recursion >

Introduction to Recursion

What is recursion?

 

  • It is a way of solving a problem
  • You take a smaller version of problem and solve it
  • You keep doing this until the complete problem is solved

 

Programming Context

Recursion is a type of program where a function calls itself with a subset of data to compute upon until a specified condition is met. This condition is termed as base/boundary condition.

Structure of Recursive Program

Any recursive program will consist of these

  • base/boundry condition
  • recursive code

 

Example

Program to calculate factorial of a number:
Factorial of a number is calculated as factorial(n) = n * (n-1) * (n-2) * (n-3) * …* 1

For e.g.
factorial(4) = 4 * 3 * 2 * 1 = 24

We can find the find the factorial using recursive approach with below code:

                        
    public static int factorial(int n) {
        if (n == 1) return 1; // base case
        return n * factorial(n-1); // recursive code
    }

Here we have the base case so we can inform the program to stop when the base condition occurs.

 

 

Diagram

Recursion call for a factorial problem.

Explaination

When we call factorial(4), the function call is added to the call stack. The call stack is a place where
all the calls made to a particular function is recorded and when the function execution is over,
it is removed from the call stack by the os.

So first factorial(4) call will be added to call stack.
factorial(4) returns 4 * factorial(3), which means its another function call.
So the OS will not remove factorial(4) from call stack but wait for the factorial(3) to execute.

Now factorial(3) will call factorial(2) which will call factorial(1) When factorial(1) is called, n==1 so it will return 1. At this point the execution
of factorial(1) is done so it will be removed from the call stack.
We return 1 to factorial(2)

Since factorial(2) was waiting for factorial(1), and factorial(1) returned 1; now factorial(2) will compute
the return value which is 2*1=2 and its execution is done and will be removed from call stack.

Similarly factorial(3) will compute 3 * factorial(2) = 3 * 2 = 6 and get removed from call stack.
Finally factorial(4) will compute 4 * factorial(3) = 4 * 6 = 24 and get removed from call stack The main function that called factorial(4) will receive 24 as the final execution output.
 

Important Note:

Whenever we use recursion we internally utilize the call stack memory as the call stack needs to store the calls made to the function.
So it may look like that we are not using any space in program but we are internally utilizing the call stack memory for the complete program execution.

Now imagine if we write a program using recursion that did not have a base case.
The program will call itself in loop infinite times. Each time it calls itself we use the call stack memory.
Since our system will have limited space, the call stack memory cannot hold all the calls and it will throw java.lang.StackOverflowError error.


Thanks for feedback.