0

am running these two functions that do the same calculation "summing the first N integers " then compare the run times for each one. The program works fine with small inputs, but the problem is when I input large numbers like 1000000, it calculates the first method "the iterativeSum()" then as soon as it gets to the the recursiveSum() it stops working.

am not sure but do you think that this might be because of the cout?

#include <stdio.h>
#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

void iterativeSum(int);
int RecursiveSum(int);


int main()
{
long long posInt;
std::cout << "Enter a positive integer: ";
std::cin >> posInt;

int start_s=clock();
iterativeSum(posInt);
int stop_s=clock();

int start_s1=clock();
cout << "\nThe recursive algorithm to sum the first N integers of "<< posInt << " is: "<< RecursiveSum(posInt) << endl;
int stop_s1=clock();

cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)/1000 << endl;

cout << "time: " << (stop_s1-start_s1)/double(CLOCKS_PER_SEC)/1000 << endl;


return 0;
}

void iterativeSum(int posInt)
{
//positive Integer >=0
int sum = 0;


//loop through and get only postive integers and sum them up.
// postcondion met at i = 0

for(int i = 0; i <= posInt;i++)
    {
        sum +=i;
    }
    //output the positive integers to the screen
    std::cout <<"\nThe iterative algorithm to sum the first N integers of " <<posInt <<" is: " << sum << "\n";
}


int RecursiveSum(int n)
{
 if(n == 1) // base case
 {
   return 1;
 }
 else
  {
    return n + RecursiveSum(n - 1);  //This is n + (n - 1) + (n - 2) ....
  }
}
Aemyl
  • 1,501
  • 1
  • 19
  • 34
Ivawen
  • 13
  • 1
  • 6
  • Do you get an error message? Or does the program just have a really long runtime? BTW: you should add the c++ tag to this question – Aemyl Feb 17 '17 at 10:14
  • no errors on the compiler , the run time is just too long , so windows will stop the program from running as soon as it gets to the recusiveSum method ? euhh i dont know how to add c++ tags though , sorry :D – Ivawen Feb 17 '17 at 23:46
  • No problem, I added it now (but you have to accept the edit). – Aemyl Feb 18 '17 at 17:59

1 Answers1

1

You may need an arbitrary precision arithmetic library like GMPlib, to avoid arithmetic overflows. And you should be afraid of stack overflow.

The call stack is often limited (to e.g. a megabyte). See this

Community
  • 1
  • 1
Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547