How can I do this without a nested loop

[aceadams]

Basically, write a program that inputs an integer n, and applies the following procedures until n=1: if n is even, divide by two, if n is odd, multiply n by 3 and add 1.

I wrote the program, but with a nested loop, however, I was not supposed to use one. How could I do it without it?

#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
if (n!=0) {
while (n!=1 && n%2==0){
n=n/2;
cout<<n<<endl;
while (n!=1 && n%2==1){
n=n*3+1;
cout<<n<<endl;
}
}
}
cout<<n<<endl;
}

[E0p9LyTq]

To repeat a block of code you need either a loop or use goto.

Using goto:

#include <iostream>

int main()
{
   std::cout << "Enter a number: ";
   int n;
   std::cin >> n;

loop: if (n != 1)
{
   if (n % 2 == 0)
   {
      n = n / 2;
      std::cout << n << '\n';
   }
   else
   {
      n = n * 3 + 1;
      std::cout << n << '\n';
   }
   goto loop;
}
     std::cout << '\n' << n << '\n';
}

Using goto is really sloppy.

Using a loop (while):

#include <iostream>

int main()
{
   std::cout << "Enter a number: ";
   int n;
   std::cin >> n;

   while (n != 1)
   {
      if (n % 2 == 0)
      {
         n = n / 2;
         std::cout << n << '\n';
      }
      else
      {
         n = n * 3 + 1;
         std::cout << n << '\n';
      }
   }
   std::cout << '\n' << n << '\n';
}

And PLEASE, learn to use code tags, it makes reading your code MUCH easier.
http://www.cplusplus.com/articles/jEywvCM9/

[E0p9LyTq]

A third possibility is loop using recursion, but that can be a major headache.

[lastchance]

#include <iostream>
using namespace std;

int main()
{
   unsigned long long n;
   cout << "Input n: ";   cin >> n;
   for( ; n != 1; n = n % 2 ? n * 3 + 1 : n >> 1 ) cout << n << '\n';
   cout << n;
}

Input n: 9
9
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Try it for n = 837799

[Enoizat]

Recursion, in this case, is not such an headache ;-)
Example (more or less copied from FurryGuy's and Lastchance's codes):

#include <iostream>

void Collatz(unsigned val);

int main()
{
    std::cout << "Please enter a POSITIVE integer: ";
    int i;
    std::cin >> i;
    std::cout << '\n';
    Collatz(i);
}

void Collatz(unsigned val)
{
    std::cout << val << '\n';
    if(1 != val) {
        if(val % 2) { Collatz(val * 3 + 1); }
        else        { Collatz(val >> 1); }
    }
}

[JLBorges]

Even when copying code, it is a good idea to stop and think for a second.

In particular, when we see a loop, think of the boundary conditions:
in this case, what would happen if n is initially zero (the user entered zero)?

Also, don't copy obfuscated code blindly: transparent code is good code.
for instance, val >> 1 does not optimize anything; people who write compilers would know at least as much about low level efficiency as the palooka who thinks that the code is being made more efficient by applying strength reduction at source code level.

For instance, in he best case scenario, foo and palooka_foo would generate the same machine code, as would bar, alt_bar, palooka_bar and palooka2_bar

unsigned int foo( unsigned int n ) { return n/2 ; }

unsigned int palooka_foo( unsigned int n ) { return n >> 1 ; }

unsigned int bar( unsigned int n ) { return n*3 + 1 ; }

unsigned int alt_bar( unsigned int n ) { return n+n+n + 1 ; }

unsigned int palooka_bar( unsigned int n ) { return ( (n<<2) - n ) + 1 ; }

unsigned int palooka2_bar( unsigned int n ) { return ( (n<<1) + n ) + 1 ; }

https://godbolt.org/g/ye8cmB

It is possible that the attempted 'clever' code may result in suboptimal machine code; as in the case of palooka_bar here; optimisers find it easier to optimise transparent code.
https://godbolt.org/g/fHibQu

While learning C++, it is important to cultivate good programming habits; basic programming hygiene.

[lastchance]

The real problem with this sequence (hailstone sequence or Collatz conjecture) is that nobody has ever proved that the sequence is guaranteed to terminate for all n. However, there is, apparently, quite a substantial financial prize if you do!


Crikey, looks like someone above really did have a bad-hair day!

[keskiverto]

@afatperson:
You probably had some logical thought that did lead to this nested version of yours:

if (n!=0) {
  while ( n!=1 && n%2==0 ) {
    n=n/2;
    cout<<n<<endl;
    while ( n!=1 && n%2==1 ) {
      n=n*3+1;
      cout<<n<<endl;
    }
  }
}

Care to share a bit of that logic?


Note:
* The sanity check on line 1 is good but not perfect. The user could give a negative number.

* If we reach line 3, then n is even and half of it is thus odd. Therefore, first time on line 5 always succeeds, unless n is already 1.

* On the other hand three times an odd value is odd too and the plus one makes it even. Therefore, the inner loop cannot iterate more than once.

* The outer loop never evaluates its body, if the n is not even. What values did you test your program with?

[E0p9LyTq]

Recursion, in this case, is not such an headache ;-)

#include <iostream>

unsigned long long GetFibNum(unsigned long long FibIndex)
{
   if (FibIndex < 2)
   {
      return FibIndex;
   }
   else // recursion if FibIndex >= 2
   {
      return GetFibNum(FibIndex - 1) + GetFibNum(FibIndex - 2);
   }
}

int main()
{
   std::cout << "Enter 0-based index of desired Fibonacci Number: ";
   unsigned long long Index = 0;
   std::cin >> Index;

   std::cout << "Fibonacci number is: " << GetFibNum(Index) << '\n';
}

Run this for an index number greater than 50, say 100, and see how long it takes to get an answer.

Using iteration (just the function shown):

unsigned long long GetFibNum(unsigned long long FibIndex)
{
   unsigned long long minusTwo = 1;
   unsigned long long minusOne = 1;
   unsigned long long answer = 2;

   if (FibIndex < 3)
   {
      return 1;
   }

   for (FibIndex -= 3; FibIndex != 0; FibIndex--)
   {
      minusTwo = minusOne;
      minusOne = answer;
      answer = minusOne + minusTwo;
   }

   return answer;
}

Both examples are easy to program, the number of function calls the recursive example has to make is annoying and a headache.

[JLBorges]

> the number of function calls the recursive example has to make is annoying and a headache.

If the same algorithm is implemented, with one version being recursive and the other being iterative,
the difference in performance between the two would not be significant.

#include <iostream>
#include <limits>
#include <ctime>
#include <cassert>

bool limits_check( unsigned long long a, unsigned long long b )
{ return a <= ( std::numeric_limits<unsigned long long>::max() - b ) ; }

// get the largest n that we can handle (with standard built in types) on this implementation
std::size_t max_nfib_ull()
{
    unsigned long long a = 0 ;
    unsigned long long b = 1 ;

    std::size_t cnt = 1 ;
    while( limits_check(a,b) )
    {
        b = a + b ;
        a = b - a ;
        ++cnt ;
    }

    return cnt ;
}

unsigned long long fib_recursive( std::size_t n, unsigned long long a = 0, unsigned long long b = 1 )
{
    if( n == 0 ) return a ;
    else if( n == 1 ) return b ;
    else return fib_recursive( n-1, b, a+b ) ;
}

unsigned long long fib_iterative( std::size_t n )
{
    unsigned long long a = 0 ;
    unsigned long long b = 1 ;

    if( n == 0 ) return a ;

    else for( ; n > 1 ; --n )
    {
        b = a + b ;
        a = b - a ;
    }
    return b ;
}

int main()
{
    const std::size_t n = max_nfib_ull() ; 

    {
        const auto start = std::clock() ;
        const auto result = fib_recursive(n) ;
        const auto end = std::clock() ;
        std::cout << "fib_recursive(" << n << ") == " << result << '\n'
                  << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ;

        assert( n>=93 && fib_recursive(93) == 12200160415121876738ULL ) ; // sanity check
    }

    {
        const auto start = std::clock() ;
        const auto result = fib_iterative(n) ;
        const auto end = std::clock() ;
        std::cout << "fib_iterative(" << n << ") == " << result << '\n'
                  << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ;

        assert( fib_iterative(93) == 12200160415121876738ULL ) ; // sanity check
    }
}

http://coliru.stacked-crooked.com/a/bc40ad354bc4dc2c
http://rextester.com/KAL43202
Note that with the Microsoft library, the resolution of std::clock() is coarser;
it didn't tick even once for either of the two versions.

[lastchance]

Recursion works just fine for this sequence (thanks @Enoizat). Since the sequence can go up (a lot) as well as down, it can unfortunately overflow, whether that uses recursion or a loop.

#include <iostream>
#include <limits>
using namespace std;

  using INT = int;               // Worth testing the different types
//using INT = unsigned long long;

INT oddLimit = ( numeric_limits<INT>::max() - 1 ) / 3;

//======================================================================

void palooka( INT n )
{
   cout << n << '\n';
   if ( n != 1 ) 
   {
      if      ( n % 2 == 0   ) palooka( n / 2 );
      else if ( n > oddLimit ) cout << "Sequence will overflow" << '\n';
      else                     palooka( 3 * n + 1 );
   }
}

//======================================================================

int main()
{
   INT n;
   cout << "Input n: ";   cin >> n;
   palooka( n );
}

Input n: 113383
113383
340150
170075
510226
255113

--- many lines removed ---

1103160598
551580299
1654740898
827370449
Sequence will overflow

Input n: 113384
113384
56692
28346
14173
42520
21260
10630

--- many lines removed ---

10
5
16
8
4
2
1

If we are to check the user's input then we should worry also whether he has entered a negative, something overflowing an integer, or even something non-numerate. So let's just assume the user has put in something legitimate.

Worrying about how one should divide by 2 in code is crass in the extreme.

[E0p9LyTq]

@JLBorges,

your example for computing a Fibonacci number recursively is very different than the one I provided, it is written so the number of function recursions is significantly reduced compared to what my example requires.

Something a good, experienced programmer would do as a matter of course.

Computing the Fibonacci number for 20, your example takes 20 function recursions.

My example takes 21891 function recursions. That is considerable overhead.

Which is what I was saying. Recursion CAN BE, not ALWAYS IS, annoying and a headache in terms of performance.

[JLBorges]

> your example for computing a Fibonacci number is very different than the one I provided,

It is a recursive implementation of the same algorithm that was used in the iterative version.

I did mention: if the same algorithm is implemented, with one version being recursive and the other being iterative ...


> My example takes 21891 function recursions. That is considerable overhead.

If that is the case, you should also write an equivalent iterative version that performs 21891 iterations.
I would suspect that that would also have a significant overhead.

Comparing the performance of iterative heap sort and recursive heap sort would be meaningful.

Comparing the performance of an iterative heap sort with a recursive bubble sort won't prove that iteration is significantly faster than recursion for a sort operation. Nor would comparing the performance of an iterative bubble sort with a recursive heap sort prove that recursion is significantly faster than iteration for a sort operation.


> Recursion CAN BE, not ALWAYS IS, annoying and a headache in terms of performance.

Performance of recursive implementations would be a concern when non-trivial destructors of local objects are involved and/or when exceptions are a possibility. It would also be a concern when the problem demands that the number of iterations (which would be equal to the number of recursive calls) must necessarily be huge.

However, recursion is never annoying; it almost always is more elegant that an equivalent iterative implementation.

[icy1]

easily repeatable version; limited to integer ranges -- exits if overflow.

#include <iostream>
using namespace std;

int main()
{
  int n;
  while (true)
  {
    cout << "Enter a positive number (0 to exit): ";
    cin >> n;
    if (n<=0)
      break;
    
    while (n!=1)
    {
      n = (n&1 ? n*3+1 : n/2);
      cout << n << endl;
      if (n<=0)
      {
        cout << "Overflow\n";
        break;
      }
    }
  }
  
  cout << "\nBye!\n";
  
  return 0;
}

In action: https://repl.it/repls/ImpressiveFinancialRuntimeerror

[lastchance]

icy1 wrote:

exits if overflow

Actually it doesn't.

Try n=2147483621 ... that OUGHT to overflow (for 4-byte ints).
The first few numbers will come out wrong. Check them by hand.

[JLBorges]

Signed integer overflow engenders undefined behaviour.

If control reaches line 14, n must be greater than zero and the if statement starting at line 18 may simply be optimised away as dead code (the optimiser simply assumes that signed integer overflow can never occur).

For example, both foo and bar could generate identical code:

int foo( int n )
{
    if( n <= 0 ) return 5 ;

    n = (n&1 ? n*3+1 : n/2);

    if( n < 0 ) return -1 ; // this can never happen 
         // or in other words, if this (signed integer overflow)
         // could happen, the entire program is already meaningless

    else return 1234 ;

    /*
    optimised to:
    if( n <= 0 ) return 5 ;
    else return 1234 ;
    */
}

int bar( int n )
{
    if( n <= 0 ) return 5 ;
    else return 1234 ;
}

https://godbolt.org/g/whxj4B

[icy1]

lastchance wrote:

Actually it doesn't.

Try n=2147483621 ... that OUGHT to overflow (for 4-byte ints).
The first few numbers will come out wrong. Check them by hand.

Ah, true, very nice catch ;P
For sufficiently big (odd) numbers, multiplying by 3 could produce a positive integer even after overflow

>> (2147483621 * 3 ) - 2**32
=> 2147483567

and then we add 1 to this, so that's why we get 2147483568. Makes sense; my checking for less than zero was incorrect -- your idea to check its value against a limit in advance is sounder.