public static int rec1(int n) {
c1++;
if (n == 1) {
return 1;
} else if (n % 2 != 0) {
return 1 + rec1(n - 1);
} else {
return 1 + rec1(n / 2);
}
}
static int c2 = 0;
public static int rec2(int n) {
c2++;
if (n == 1) {
return 1;
} else if (n % 2 != 0) {
return 1 + rec2(n - 1);
} else {
int sum = 0;
do {
n = n / 2;
sum++;
} while (n % 2 == 0);
if (n == 1)
return 1 + sum;
return 1 + sum + rec2(n - 1);
}
}
public static void main(String[] args) {
System.out.println(rec1(3128) + "; iterations: " + c1);
System.out.println(rec2(3128) + "; iterations: " + c2);
}
Output:
16; iterations: 16
16; iterations: 5
If you studied CPU architecture you should know every function call creates a new stackframe and new local variables with each call, taking up a lot of memory.
SP = stack pointer register
BP = base pointer register
They are in your CPU, BP points to the base of the stack and SP points to the top stackframe aka the function call being executed by the CPU at a given moment.
Recursion is very inefficient memory-wise so the second function, which is still recursive but has an iterative component for powers of 2, is obviously superior.