Thread: Correct algorithm, wrong result (cout problem?)

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    3

    Correct algorithm, wrong result (cout problem?)

    Hi everyone,

    I am a C++ newbie. Here is the code (3n+1 algorithm) I am having problem with. No matter what the input number is (to the alg function), the result is always the same (namely, 16384). The algorithm seems correct to me, I guess the problem is with the cout in the main function. I don't know how to fix it. THX in advance.

    Code:
    #include <iostream>
    
    int alg(int, int);
    
    int main() {
      using namespace std;
       
      int result = alg(300,1);
      
      cout << result;
      
      cin.get();
    }
    
    //counter = 1
    int alg(int n, int counter) {
      using namespace std;
    
      if (n == 1)
        return counter;
      else {
        if (n % 2 == 1)
          alg(3*n+1, ++counter);
        else
          alg(n/2, ++counter);
      }
    }

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    It's a horrible algorithm, no offence. No need to do this recursively at all.

    But the mistake is that you don't have a return statement for "alg" for every path of execution. That's all I'm going to say.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    My compiler produces a warning:

    "ComeauTest.c", line 27: warning: missing return statement at end of non-void
    function "alg"
    }
    ^
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    3
    Quote Originally Posted by EVOEx View Post
    It's a horrible algorithm, no offence. No need to do this recursively at all.

    But the mistake is that you don't have a return statement for "alg" for every path of execution. That's all I'm going to say.
    First of all, THX for your fast and kind reply.
    You are right, it can be done with a simple for loop :-D
    However, are you implying that basically every function that has no return statement for every path of execution will output something crazy even if there is an actual return value? If so, why is that?
    And just how does my complier know that there is no return statement for every path of execution for this specific algorithm, when in fact the Collatz conjecture seems to be true? Or has my computer found the exception? Lol.
    Last edited by dember; 11-02-2009 at 05:53 PM.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    int alg(int n, int counter) {
      using namespace std;
    
      if (n == 1)
        return counter;
      else {
        if (n % 2 == 1)
          alg(3*n+1, ++counter);
        else
          alg(n/2, ++counter);
      }
    }
    The bold part is the only part of the function that returns something meaningful. If you don't return anything from other parts of the function, whatever happens to be at a particular spot on the stack gets used as the "result".

    And it should be pretty easy for the compiler to see, that the if branch returns something whereas the else part doesn't. Turn on warning diagnostics (e.g -Wall for GCC)

    What it should be:

    Code:
    int alg(int n, int counter) {
      using namespace std;
    
      if (n == 1)
        return counter;
      else {
        if (n % 2 == 1)
          return alg(3*n+1, ++counter);
        else
          return alg(n/2, ++counter);
      }
    }
    Now you can easily see that each execution path through the function ends with a return statement.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    3
    Ok, I get it now. Thank you, anon.

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by dember View Post
    However, are you implying that basically every function that has no return statement for every path of execution will output something crazy even if there is an actual return value? If so, why is that?
    If there is no return value on every possible path, how does the compiler know what should be returned? Voodoo magic?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buidl Library with ./configure script
    By Jardon in forum C Programming
    Replies: 6
    Last Post: 07-24-2009, 09:36 AM
  2. Dijkstra algorithm problem.
    By apacz in forum C++ Programming
    Replies: 5
    Last Post: 05-28-2005, 04:16 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

Tags for this Thread