I needed some help to complete this exercise because I found that it was not as straightforward as it seemed. The first thing I had to learn was the distinction between signed and unsigned int. There was a lengthy discussion on usenet about it. Basically, for this exercise an unsigned int is a value that can only be positive.

But below is some of the questions and discussions about this exercise from the c++ usenet group.
_______________

The program takes a number as input. If the value input is even, the
function should return HALF of the value input. If the value input is
odd, the function should return three times the value input + 1.

This function should repeatedly be called until it returns 1.

I originally thought this program could be easily done by using a while
loop, but i could not figure out how to do it. SO i think that it can be
easily done if i make the function recursive. That is, it should keep
calling itself until it returns 1 to main.

How can i do this?
--------------------
This only calls the function twice

#include <iostream>

using namespace std;

unsigned int half(unsigned int);

int main()
{

    unsigned int number(0);

    cout << "Input a number: \n";
    cin >> number;

number = half(number);

}

unsigned int half(unsigned int inputno)
{
    unsigned passback(0);
    if(inputno != 0)
    {

if(inputno % 2 == 0)
{
passback = inputno / 2;
cout << passback;
}
else
{
passback = (inputno * 3) + 1;
cout << passback;
}

return passback;
}
}

---------------------
Richard Heathfield reply:

#include <iostream>

unsigned long int f(unsigned long int n)
{
  std::cout << " " << n;
  (n == 1) || (n = f((n % 2 == 0) ? n / 2 : 3 * n + 1));
  return n;
}

int main()
{
  unsigned long int n = 0;
  std::cout << "Input a number:" << std::endl;
  std::cin >> n;
  f(n);
  std::cout << std::endl;
  return 0;
}

Beware range errors.

Sample run:

Input a number:
27
 27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 
91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 
1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 
850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 
7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 
1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 
70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

--------------

Thank you sir - this works, but to tell the truth i wanted to simplify
the program so it is easy to read:

#include <iostream>
using namespace std;
unsigned int half(unsigned int);

int main()
{
        unsigned int number(0);

        cout << "Input a number: \n";
        cin >> number;

        half(number);
}

unsigned int half(unsigned int inputno)
{
        cout << inputno << '\n';
        (inputno==1)||(inputno=half((inputno % 2 == 0) ? inputno/2:
3*inputno + 1));
        return inputno;
}

---------

The second line of the function definition is way too cryptic for a
novice to understand. I have been trying to express this as a if - else
statement instead, but cant get it to work.

This is a interesting toy program to illustrate recursion - but i am
finding the logic of it impenetrable. There was no requirement for me to
implement this as a recursive function - which i suppose is an advanced
method, i just could not work out how to express a repreated call in a
simple while loop - which would have been even clearer. So could you
please show how i could put a while loop in main to repreatedly call the
function?

I think the test condition should be something like while(inputno != 1).
If i could do that, then it might be possible to re-write this in a
clearer way - that i understand.

--------------

R. Scott Mellow reply:
I think this covers it.

unsigned long int f(unsigned long int n)
{
    std::cout << ' ' << n;
    if(n != 1)
    {
        if(n % 2 == 0) // if n is even
        {
            n = f(n/2);
        }
        else
        {
            n = f(3 * n + 1);
        }
    }

    return n;
}
--------------
Bart v Ingen Schenau reply:

Your original thought was correct. This is a problem that lends itself
very good for an iterative solution (i.e. a loop).
Here is how you would go from the problem statement to a loop:

- function should be called repeatedly -> while('something')
- until it returns 1 -> 'something' == 'retval != 1'
- how do we make progress? function returns a value that changes with
its input (parameter) -> call function with the last result it
returned.
Putting this all together:
  while (number != 1)
  {
    number = func(number);
  }

There you have your loop. Now it is up to you to put that into a working
program.

> > SO i think that 
> > it can be easily done if i make the function recursive. That is, it
> > should keep calling itself until it returns 1 to main.

There you have a big problem. How can a function return a value to main
when it keeps calling itself?
You need some other condition to end the recursion, something that
depends on the parameter(s) that are passed to the function.

If you really want a recursive solution, take a good look at the code
that Richard posted. (One hint: a statement like 'A || B' is equivalent
to 'if (A || B) /*empty*/;')

> > 
> > How can i do this?
> > --------------------
> > This only calls the function twice

Actually, I see only one call to the function.
For a function to be recursive, it has to call itself (either directly
or indirectly through some other function(s)).

--------------------

Francis Glassborow reply:

Someone mentioned range errors I did not note any further discussion of this.

Two points should be noted:

1) the current value should always be checked prior to trebling it to ensure that you do not exceed the maximum value allowed by the integer type you elect to use.

2) You should use the largest available integer type. As the values are essentially unsigned  I would suggest that you use unsigned long.


My final comment is that I am think someone should have commented on picasso's name for the work function; 'half' is not an appropriate name. I do not think there is any realistic name other than generic ones such as func. 

-----------
Hi, I dont understand the significance of these points. I just thought
that as long as the number was not 1, the function should keep calling
itself. Richard Heathfield gave me a example of a recursive function and
used unsigned long in his example- i did not understand why this was
necessary. I have tried to figure why it might be useful, but cant work
it out - so please could you expain this further from the start please?

----------
The algorithm     results in periodic growth in the numbers in the sequence. For example, starting with 7
7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20
-> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Note that before terminating the start value of 7 (which only requires 3 bits) involves using 52 (which requires 6 bits)

Now using an unsigned long allows you to use all values that can be represented in 32-bits (more on some systems) but how do you know before you start what the largest number in the sequence will be? That is why you have to check before you multiply by 3 and add 1 and why it is advisable to use the largest available integer type (reduces the number of cases where you would need to abort. The alternative is to use an unlimited integer type (though even here you might ultimately hit a number that your system could not store. In 2007 pi was calculated to 51 539 600 000 places. I initially considered downloading it to my desktop but I thought again when I realised how much storage that would use.
-------------------
Bart v Ingen Schenau reply:

You should use the largest available integer type, because even a modest
input value can lead to enormous intermediate values before dropping
back to 1.
If you look at the output of the run that Richard made, he started with
27, which is a modest value.
But the largest value in that sequence was 9232 which is already quite
large. Furthermore, there is no clear relation between the starting
value and the largest value in a sequence, so it is impossible to
predict how much storage you need. It is possible that an input of say
29 results in a sequence that reaches up to 66000, which is too large
to store in a simple int (portably that is).

The reason for checking if the number is small enough before trebling is
based on the same argumentation that you can't know the largest number
you will need and additionally, if the number gets too big for unsigned
long, it will wrap around and there is no guarantee any more that the
sequence will ever end with the value 1. You might get into an endless
loop with wrap-arounds.
It is better to detect such problems before they occur and just
terminate the program.

-----------------
Richard Heathfield reply:

<snip>
 
> > You should use the largest available integer type, because even a
> > modest input value can lead to enormous intermediate values before
> > dropping back to 1.

Right. And unsigned integers at least avoid undefined behaviour even 
if they get the answer wrong because of wraparound.

> > If you look at the output of the run that Richard made, he started
> > with 27, which is a modest value.
> > But the largest value in that sequence was 9232 which is already
> > quite large. Furthermore, there is no clear relation between the
> > starting value and the largest value in a sequence, so it is
> > impossible to predict how much storage you need. It is possible
> > that an input of say 29 results in a sequence that reaches up to
> > 66000, which is too large to store in a simple int (portably that
> > is).

For inputs up to and including 10, the largest output is 52, which 
happens for two of the inputs.

For inputs in the range 11-20, the largest output is 160 (for 15).

For inputs in the range 21-254, the largest output is 9232 (for 27, 
and I must confess I knew this when choosing a test value - it's 
mentioned in GEB).

At 255, we find a 13120, and at 447 the max jumps to 39364. For an 
input of 937 the highest value encountered is a fairly large 
250504.

I didn't check for wrap, however, so these values could conceivably 
be erroneous.