Five Steps to solve Recursive problems
Recursion is needed for solving graph and DP problems
Recursion is the technique of a function calling itself repeatedly till the base condition is satisfied.
It reduces the length of our code. Recursion is helpful for solving Graph Traversal and Dynamic programming types of problems.
5 steps to solve a problem using recursion:
Step 1. Find the base case The base case is the condition, which tells the function when to stop.
Problem Statement: Given an input n. Calculate the sum of all the integers from 1 up to n. Solve it using a recursive function.
When there is only 1 element, sum is 1. In our example problem. base case is when n =1, answer = 1.
Step 2. Write some example cases with consecutive inputs (preferably more than 5 example)
n = 5; answer = 1 + 2 + 3 + 4 + 5 = 15
Step 3. Find a pattern between two consecutive answers
n = 4; sum(4) = 1 + 2 + 3 + 4 = 10
n = 5; sum(5) = 1 + 2 + 3 + 4 + 5 = 15 = sum(4) + 5
Step 4. Generalize a pattern in function terms
n = 5; sum(5) = 1 + 2 + 3 + 4 + 5 = 15 = sum(n-1) + n
n = 4; sum(4) = 1 + 2 + 3 + 4 = 10 = sum(n-1) + n
Step 5. Write code using recursion, with base case
int sum ( int n ) {
if( n == 1)
return 1;
return n+ sum(n-1);
}
For more details you may check this video:
