DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Dealing with Recursion as a Beginner
Gourav Singh Rawat
Gourav Singh Rawat

Posted on

Dealing with Recursion as a Beginner

What is Recursion

A function calling itself. Well that's what most of us know.
But something that will help a beginner with recursion is that recursion follows a Mathematical concept that is PMI - Principle of Mathematical Induction. For those who are afraid of maths this'll be a punch. But to know more about this we have to imagine how recursion works...

Calculate Sum of Digits of a Number

Imagine I have a number 123 and we need to calculate the sum of individual digit in this number i.e. 1+2+3 = 6.
We can do this iteratively easily, using for and while loops. But in recursion we take a Base case that'll return some integer like

#include <bits/stdc++.h>
using namespace std;

int SumOfDigits(int number){
  // Base case
  if (number==0){
    return 0;
  };
  // Recursion & Calculation
  number = SumOfDigits(number/10)+(number%10);
  return number;
};
Enter fullscreen mode Exit fullscreen mode

Here what base case is doing :

 // Base case
  if (number==0){
    return 0;
  };
Enter fullscreen mode Exit fullscreen mode

We know that once number gets to 0 it'll return 0. That means that if my number reaches end of the digit.
We are splitting the whole number into smaller numbers that's what recursion is about, split your problem into the smaller problems. Once you find the answer to smaller problems you'll find your answer to main problem eventually.

What we did here:

  // Recursion & Calculation
  number = SumOfDigits(number/10)+(number%10);
  return number;
Enter fullscreen mode Exit fullscreen mode

We split number without last digit every time recursion is called. Once there will be only one digit left say - 1, this is where our base case comes into action, as 1/10 will give 0 and it'll eventually return answer to be 0. In manner 12 will be solved as base case of 1 returns 0 we added first and last digit of the number i.e. 1+2 = 3. Once this is done consecutive recursion will split 3 and 3, now as the previous recursion returned 3, we again added last and first value i.e. 3+3 = 6.
This might be somewhat tough to understand in the beginning, but once you get practice of this by dry running your code in paper you'll start to understand it even more.

NOTE

One more reason why we used base case to be 0 before conclusion, is that since our recursion doesn't stops by itself and it keeps making the number shorter this will give Runtime error or Segmentation fault at sometime. To avoid this we added a base case that's returning 0 once there is only one element is left in the number.
Hope this helps to get a little clear image of recursion. Keep practicing it on problems and you'll get through it.

Top comments (2)

Collapse
 
pauljlucas profile image
Paul J. Lucas

Instead of bits/stdc++.h, you need iostream. The "bits" header isn't standard. See here for details.

Your line that reads:

};
Enter fullscreen mode Exit fullscreen mode

is wrong: it must not have a ; there. The only time a ; follows a } is for a class, struct, union, or enum declaration.

Collapse
 
seek4samurai profile image
Gourav Singh Rawat • Edited on

You do have a right point but when solving questions and working on algorithms I guess including bits is best option to save time while writing headers. This header file do have it's own pros and cons...Thanks for contributing.

12 Gorgeous UI Components for Your Design Inspiration

>> Check out this classic DEV post <<