Prerequisite:
Please read Subroutine Call before studying recursion.
Introduction:
Recursion is a concept in computer science and mathematics where a parameterized function calls itself in order to solve a problem.
The function solves the problem by calling itself with a simpler version of the same problem by passing smaller input version of parameters, effectively breaking it down into more manageable pieces.
This process is continued on until the function reaches a base case, which is a condition that stops the recursion. Below figure illustrates the same.
Suppose there is a problem which can be converted into function as below:
f(n)=2*n+f(n-1)+n%2 and f(0)=0
Then the above function can be solved using recursion as below for n=3.
f(3)=2*3+f(2)+3%2
=6+(2*2+f(1)+2%2)+1
=6+4+(2*1+f(0)+1%2)+0+1
=10+2+0+1+0+1=14
Implementation:
To solve a given problem using recursion first we need to convert given problem in the form of mathematical function where problem statement depends upon itself with smaller version of input parameters. There are three steps to convert a problem in the recursive solution. These are 1. Hypothesis 2. Inductive Step and 3. Base Condition.
Below is the example of calculating factorial of a number. Suppose fact(n) calculates the factorial of n. Then we can write it as:
fact(n)=!n --> This step is called Hypothesis step in the recursion(We will discuss it in detail)
But we have to write the above function in the term of fact(n) only. We can rewrite it as below:
!n=n*!(n-1)
=> fact(n)=n*fact(n-1)--> This step is called Inductive step in the recursion(We will discuss it in detail)
The above step converts the calculation of the factorial of number in the terms of our assumed function fact(n) but it is missing the stop condition. Below we understand it by an example. Suppose we want to calculate fact(3), so below will be the derivation based on the above function definition mentioned in the inductive step.
fact(3)= 3*fact(2)=3*2*fact(1)=3*2*1*fact(0)=3*2*1*0*fact(-1)=3*2*1*0*-1*fact(-2) . . .
In the above derivation we can see that calculation was correct till green color but after that it gets wrong and chain continues infinitely by unnecessarily expanding the fact(n) which is highlighted in the red color.
So we need to stop our function expansion on some valid point in the derivation. This point is called base condition. In the above expansion we can easily say till fact(0) expansion was correct after that expansion of fact(n) must not be allowed. So in the expansion of fact(n), if n=0 expansion must be stopped with value of fact(n)=1 where n=0.
So above recursive solution can be redefined as
fact(n)=n*fact(n-1) if n>0 --> This step is called Inductive step.
fact(n)=1 if n=0--> This step is called Base condition in the recursion(We will discuss it in detail)
Right now the above recursive relationship to compute the factorial of a number is complete and it can be easily converted to any programming function/method/subroutine etc. Below is the algorithm to calculate the factorial:
fact(n)
{
if(n==0)
{
return 1
}
return n* fact(n-1)
}
Based on the above explanation, we need to follow 3 below steps to convert a problem in the recursive solution:
Problem - Given a number n, Calculate the sum of numbers from 1 to n.
-
Hypothesis - Here we sort out all valid input parameters and define a parameterize function
- Find out all valid inputs
- Envisage a function with all input parameters and assume it calculates the desired result
- Write down the above function with solution
- Re-Write above function with smaller inputs
SUM(N)=1+2+3 . . . +n - Inductive steps - Here based on the above defined function a recursive relationship is established. Below are the method to establish recursive relationship
- Rewriting defined function for smaller input parameters and establish recursive relationship
- Drawing a tree structure for defined function and decide recursive relationship
- Base condition - This is the condition on valid input parameters which defines the criteria to stop the recursion. In the above example we can say if value of input parameter n is 0 then its result is also 0. This is the most important step in the recursion.
We can define the above mentioned problem as below by adding base condition to inductive step:
SUM(n)=SUM(n-1)+n if n>0
SUM(n)=0 if n==0
SUM(n)= not defined if n < 0
SUM(n-1)=1+2+3 . . . +(n-1)
So sum of n numbers will be
SUM(n)=SUM(n-1)+n
Recursion tree for SUM(n) is given below:
Below is the recursive solution for above mentioned problem:
- SUM(n)
- {
- if(n<0)
- {
- throw error
- }
- if(n==0)
- {
- return 0;
- }
- return SUM(n-1)+n
- }
- Main function calls the recursive function
- Recursive function calls itself as a subproblem of given problem
- Called child recursive function itself acts as an independent problem and it again calls itself as part of subproblem for final solution
- Here a chain of recursive function call exists in the RAM memory of the system where every function waits for the result from its child recursive function
- This chain of called recursive functions call itself again and again and continued on until a called recursive function executes the base condition of the recursive function. Base condition is the point which returns some value rather than recursive function again. Here chain of recursion breaks down and the backward execution of recursion chain starts.
- Once call returns back from the function executing the base condition, its parent function gets executed and result is returned back to the next level of parent function. This process is continued on in the bottom up fashion for solution preparation where child functions get fully executed and get deallocated from the RAM memory
- Once all waiting functions get executed, final result is computed and sent back to main function
Below is the java code implementation of the above mentioned recursive problem
public class SumByRecursion {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int result = getSum(4);
System.out.println(result);
}
private static int getSum(int n) {
// TODO Auto-generated method stub
if(n<0)
{
throw new Exception("Invalid Input");
}
if(n==0)//Base condition
{
return 0;
}
return getSum(n-1)+n;//Inductive step
}
}