Recursive Squaring

This one neatly solves problem of log n multiplications to calculate nth power of of some number. It goes in two stages, calls self recursively with half power until it reaches power 0 or 1 and then squares results. If power was not even correction is required, additional multiplication with base.

static long pow(long base, int n){ if(n==0) return 1; if(n==1) return base; long acc = pow(base, n/2); acc *= acc; if(n%2 == 0) return acc; return base * acc; }

If we want to see how it works and how many times it calls self we can insert debug code:

static long powDbg(long base, int n, int depth){ for(int i = 0; i < depth; i++) System.out.print("-"); System.out.println(n); if(n==0) return 1; if(n==1) return base; long acc = powDbg(base, n/2,depth+1); acc *= acc; for(int i = 0; i < depth; i++) System.out.print("-"); System.out.println(n); if(n%2==0) return acc; return base * acc; }

Should have been included it in previous blog entries about recursion but better late than never.