Digital Root of Large Integers using Recursion in C++

In this tutorial, we will learn how to calculate the digital root of a given long number i. We will be using a recursive approach for the same.

We will learn what a digital root means and also how to implement a program that calculates it in C++.

Digital Root of Large Integers using Recursion in C++

What is digital root?

Consider the number 5674. Add the digits of the number. We get 5+6+7+4=22. We still have a 2 digit number. Continue the process until we get a single digit integer. Add 2+2=4. The result is a single integer. We can stop here.

Therefore, the digital root of 5674 is 4.

Integer approach: Digital Root of Large Integers

Here I will be implementing an integer based approach for calculating the digital root of a number. Be warned, it won’t work for very very large numbers. I have used long type for the numbers but even after using long long type I won’t be able to calculate the digital root for say, 4834693653478693748694386463746949369436693849384201.

But this method works for smaller numbers, say 684741. The approach is simple. You get each digit by dividing by powers of 10 and keep adding it. For each number, we make a recursive call until the resultant integer becomes zero. Here is the code in C++.

Code:

```#include <iostream>
using namespace std;
#include<cmath>
#include <string>
#include <stdio.h>
#include <string>
#include <sstream>
long digiRoot( long a){
int result=0;
int res=0;
if(to_string(a).length()==1)
return a;
else{
int temp=0;
int k= to_string(a).length();
for(int i=0; i<k; i++){
long h=0;
h=floor((fmod(a, pow(10, i+1))-temp)/(pow(10, i)));
temp=fmod(a, pow(10, i+1));
res+=h;

}

}
return digiRoot(res);
}

int main()
{

int n;
cout<<"Enter the integer to find the Digital Root"<<endl;
cin>>n;
int result= digiRoot(n);
cout<<endl<<result;

return 0;
}```

Ouptut:

```Enter the integer to find the Digital Root

684741

3```

String based approach: Digital Root of Large Integers

Let us say we have a number  43898365436436576389653787347023584702818074822741. We can get this number in the string format and then process it. At each call, each digit is converted to an integer and then processed. The C++ implementation:

Code:

```#include <iostream>
using namespace std;
#include<cmath>
#include <string>
#include <stdio.h>
#include <string>
#include <sstream>

int digiRootStr(string mynum){

string k="";
if(mynum.length()==1)
{

stringstream tonum(mynum);
int x = 0;
tonum >> x;
return x;
}

else{
int h=0;
for(int i=0; i< mynum.length(); i++){
char j= mynum.at(i);

int g=0;
g=j-'0';
h+=g;

}
k= to_string(h);
}
return digiRootStr(k);
}

int main()
{

string n;
cout<<"Enter the integer to find the Digital Root"<<endl;
cin>>n;
int result= digiRootStr(n);
cout<<endl<<result;

return 0;
}```

Output:

```Enter the integer to find the Digital Root

43898365436436576389653787347023584702818074822741

9```