Recursion not working inside a loop in C++

Question

I have a problem to solve in C++ which is as follow : 1 + (1/2!) + (1/3!) + (1/4!) + (1/5!)... and so on

The code I have written for the same is as follows

#include <iostream>
using namespace std;

int fact(int);

int main()
{
    int n; float sum=0;
    cout<<"Enter number of terms:";
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        sum = sum + (float)(1/(fact(i)));
    }

    cout<<endl<<"The sum is :"<<sum;
    return 0;
}

int fact(int x)
{
    if(x == 0 || x == 1)
        return 1;
    else
        return x * fact(x-1);
}

The above code is not returning any output. Earlier I have computed factorial without using for loop. And the recursion has worked.

Answer 1

The culprit here is Integral Division in C++.

If one of the operand is integer C++ performs integral division which by nature discards fractional part. If at least one of them is float or double the result is kept. For example check output for following statements.

cout<<(1/5);   // Gives 0 Umm.. weird

cout<<(1/5.0); // Gives 0.2 Umm.. works

cout<<(1.0/5)  // Gives 0.2 Umm.. also works

Now in your code, modify:

sum = sum + 1/fact(i);

to

sum = sum + 1/(1.f*fact(i));

or typecast explicitly at least one of operand.

sum += 1/(float)(fact(i));

Also note that:

(float)(1/5)

will not work as the typecasting occurs after integral division so make sure at least one of operand is float or double before division.

You can read more on how integral divison works in C++.

Full working code for your reference :

#include <iostream>
#include <iomanip>  //for precision
using namespace std;

int fact(int x){
    if(x == 0 || x == 1)
        return 1;
    else
        return x * fact(x-1);
}

int main(){
    int n; 
    float sum=0;

    //to set precision upto 3 decimal places
    cout << std::fixed;
    cout << std::setprecision(3);

    cout<<"Enter number of terms: ";
    cin>>n;

    for(int i=1;i<=n;i++){
        sum = sum + 1/(1.f*fact(i));
        //sum += 1/(float)(fact(i));  or use typecasting like this
    }

    cout<<"The sum is :"<<sum<<endl;
    return 0;
}

To know more about setting precision check this.

Answer 2

The problem is your base case in the recursion:

int fact(int x)
{
    if(x == 0 || x == 1)
        return 0;
...

which makes all factorials zero, and then you divide by zero: 1/(fact(i)) and crash your program.

The proper base case is 1, and you need to avoid integer division with 1.0f/fact(i).

You would have spotted the base-case bug quickly if you had tested the fact function on its own first.

Answer 3

PROBLEM

The problem here is the lack of proper type casting in widening primitive conversions. Any operation between 2 int operators will produce an int, and casting the whole expression will result in loss of value. In this case, the "sum = sum + 1/fact(i);" line has two problems. fact(i) being an int value, 1/fact(i) will return an int (read 0, for i>1) and then the variable sum is an int, so even if 1/fact(i) returns a double value, sum will just be able to hold the implicitly cast int value. Kindly refer https://learn.microsoft.com/en-us/cpp/cpp/type-conversions-and-type-safety-modern-cpp?view=vs-2019

SOLUTION

Multiple solutions are possible for this.

1. The easiest - you could just declare sum to be a double and change the line inside the loop to - sum = sum + 1.0/fact(i);

2. Or, you could declare sum to be a double and typecast or declare the return type of fact(i) to be a double.

And just to add lest I forget, I suppose you'll actually return or print the final sum value to check this code.

Hope this is helpful and clear!

Answer 4

I corrected code snnipet.
1.) You had return 0; in main before printing sum.
2.)In factorial function you have return 0 which will give infinity when divided by any number. It will cause exception. #include using namespace std;

int fact(int);

int main()
 {
  int n; float sum=0;
  cout<<"Enter number of terms:";
  cin>>n;

  for(int i=1;i<=n;i++)
  {
    sum = sum + (float)(1.0/(fact(i)));
  }
  cout<<"The sum is :"<<sum<<endl;

  return 0;
  }

 int fact(int x)
 {
    if(x == 0 || x == 1)
       return 1;
    else
       return x * fact(x-1);
 }

Answer 5

You can avoid recomputing the factorial if you keep a running term inside your loop:

inline float inv_fseries(std::size_t lim) {
  float term = 1.f;
  float sum = 1.f;
  for (std::size_t i = 1; i <= lim; ++i) {
     term /= static_cast<float>(i);
     sum += term;
  }
  return sum;
}

The static_cast can also be avoided by using a float running variable, but care must be given to avoid floating-point related off-by-one errors (not every integer can be represented by a float)

inline float inv_fseries(std::size_t lim) {
  float term = 1.f;
  float sum = 1.f;
  float const bound = static_cast<float>(lim) + 0.5f;
  for (float i = 1.f; i <= bound; ++i) {
     term /= i;
     sum += term;
  }
  return sum;
}

---

One could argue that this has worse runtime because we replaced integer point operations with floating point operations. But at the point where this becomes an issue your limit n is so large that the whopping O(n^2) in the original algorithm versus this algorithm's O(n) outweighs all overhead from floating-point multiplications.

On a related note: never plug user-provided numbers into recursive functions if the recursion depth depends on those numbers. Literally the name of this website. ;)