We cannot use induction to prove that this program terminates, because not every recursive call uses an argument smaller than the one given.
👍 g++ collatz.cpp && ./a.out
3
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
👍 g++ collatz.cpp && ./a.out
11
11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40
-> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2
-> 1
👍 g++ collatz.cpp && ./a.out
17
17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10
-> 5 -> 16 -> 8 -> 4 -> 2 -> 1
👍 g++ collatz.cpp && ./a.out
23
23 -> 70 -> 35 -> 106 -> 53 -> 160
-> 80 -> 40 -> 20 -> 10 -> 5 -> 16
-> 8 -> 4 -> 2 -> 1
👍 g++ collatz.cpp && ./a.out
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
👍 cat collatz.cpp
#include <iostream>
using namespace std;
int collatz(int N) {
if (N == 1) {
cout << 1 << endl;
return 1;
}
cout << N << " -> ";
if (N % 2 == 0)
return collatz(N/2);
else return collatz(3*N+1);
}
int main() {
int N; cin >> N;
collatz(N);
}
👍 g++ collatz_calls.cpp && ./a.out
3
collatz(3)
collatz(10)
collatz(5)
collatz(16)
collatz(8)
collatz(4)
collatz(2)
collatz(1)
👍 cat collatz_calls.cpp
#include <iostream>
using namespace std;
int collatz(int N, int i) {
cout << string(i, ' ')
<< "collatz(" << N << ")"
<< endl;
if (N == 1) {
return 1;
}
i += 2;
if (N % 2 == 0)
return collatz(N/2, i);
else return collatz(3*N+1,i);
}
int main() {
int N; cin >> N;
collatz(N, 0);
}
ch5.1 Recursive Algorithms p225/204 of