why 'code01' is more efficient than 'code02'? it seems like both codes are still getting the remainder after all the operation finished.

// code01

function power(base, exponent) {
  if (exponent === 0) return 1;

  const half = parseInt(exponent / 2);
  const temp = power(base, half);
  const result = (temp * temp) % 94906249;

  if (exponent % 2 === 1) return (base * result) % 94906249;
  else return result;
}

//code02

function power(base, exponent) {
  if (exponent === 0) return 1;

  return base * power(base, exponent - 1) % 94906249;
}

CodePudding user response：

The first one uses exponent / 2 in the recursion, the second one exponent - 1.

Repeated division gives you logarithmic runtime, repeated subtraction gives you linear runtime.

Compare:

Division with a factor of 2 means 4 steps for input 8, 5 steps for input 16, 11 steps for input ~1000. Subtraction of 1 means 1000 steps for input 1000. 11 is a lot less than 1000.