DEV Community

Ashis Chakraborty
Ashis Chakraborty

Posted on

Steps to solve Recursive 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:

Problem Statement: Given an input n. Calculate the sum of all the integers from 1 up to n. Solve it using a recursive function.

Step 1. Find the base case The base case is the condition, which tells the function when to stop.
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);                    
 }

Enter fullscreen mode Exit fullscreen mode

For more details you may check this video:

Solve Recursion in Five Steps | @designUrThought - YouTube

Welcome to @designUrThought for an in-depth exploration of recursion, a fundamental concept in computer science and programming! Whether you're a coding nov...

favicon youtube.com

Top comments (0)