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