iteration and recursion question

This is a discussion on iteration and recursion question within the C++ Programming forums, part of the General Programming Boards category; Hi all, me again I had someone ask me whether the sum of 1/n as n tends to infinity converges ...

  1. #1
    Registered User Stonehambey's Avatar
    Join Date
    Jan 2008
    Location
    Kent, UK
    Posts
    118

    iteration and recursion question

    Hi all, me again

    I had someone ask me whether the sum of 1/n as n tends to infinity converges or not(that is 1+1/2+1/3+1/4+...+1/n). Now as a mathematician I can show that it doesn't quite easily. But I thought I would give it a go in c++. While it won't prove anything, it can demonstrate that for large numbers there doesn't seem to be an upper bound, plus I thought it would be fun!

    So I created a couple of functions, one using recursion and the other using iteration. Here they are.

    Code:
    long double sum(long double n)
    {
          if(n==1.)
          {
                  return 1.;        
          }
          
          long double d = (1/n) + sum(n-1);
          return d;
    }
    Code:
    long double sum2(long double n)
    {
         
         long double d = 0;
         
         for(double i=1;i<=n;i++)
         {
              d += 1/i; 
         }
         
         return d;
    }
    I then wrote a simple main which checked to make sure n was greater than or equal to one and, if it was, would call one of these functions to show the sum.

    Now both the functions seem to work except for one difference. When I set n to one million and the main calling the first function, the program simply closes. But when I tell the main to call the second (iterative) function, it works fine.

    I thought it might be the variable types I was using (which is why I changed them to long double) but it didn't seem to make a difference, so I'm simply wondering what the difference is?

    For completeness, here is the main

    Code:
    int main()
    {
        long double n;
        long double ans;
        
        cout << "Enter your value of n: ";
        cin >> n;
        if(n>=1)
        {
                ans = sum2(n);
                cout << "The sum is " << ans << endl;
        }else
        {
             cout << "Value of n makes no sense!";     
        }
        
        getch();
        return 0;
    }
    as you can see, this particular main calls the second function.

    Kind Regards

    Stonehambey

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,743
    When I set n to one million and the main calling the first function, the program simply closes.
    There is a limit to the stack, and such a large number of recursive calls probably went beyond that limit.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    The sum from n == 1 to N of 1/n is going to be something on the order of ln(N) (since the integral of 1/x is ln(x)). By drawing diagrams it's pretty easy to put both lower and upper bounds on the sum. Since ln(N) goes to infinity so slowly you will have trouble reaching very large sums (but you probably know that already).

  4. #4
    Registered User Stonehambey's Avatar
    Join Date
    Jan 2008
    Location
    Kent, UK
    Posts
    118
    Thanks for the replies

    There is actually no upper bound on the series, but since we're not talking about C++ really anymore, it's probably best I just link you to my site (for those who're interested in the maths )

    http://stonehambey.com/?p=62

    Thanks once again,

    Stonehambey

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function crashes.
    By samus250 in forum C Programming
    Replies: 9
    Last Post: 01-16-2008, 01:58 PM
  2. Recursion vs. Iteration
    By simpleid in forum C++ Programming
    Replies: 5
    Last Post: 06-06-2007, 01:17 PM
  3. What is the difference between Recursion and Iteration?
    By neo_phyte in forum C Programming
    Replies: 12
    Last Post: 09-13-2006, 02:13 AM
  4. Iteration and recursion?
    By Munkey01 in forum C++ Programming
    Replies: 15
    Last Post: 01-18-2003, 07:16 PM
  5. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 08:24 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21