It seems hard to come up with an argument showing that one always
reaches the number 1. The sequence seems to behave quite erratic.
For instance, for 27 we get the following sequence.
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.
Actually, it is a famous open (meaning unsolved) problem to prove
that for every n,
eventually the number 1 is reached. This problem is known as: Collatz'
problem. Therefore, it could be the case that for some n the
sequence can go on for ever and ever without ever reaching 1.
So, we cannot be sure that the evaluation of steps n terminates for every n.
When defining recursive functions it is important to make sure that
they do terminate.
In this course we show how one can make sure only to
define terminating recursive functions.