# Pure recursion in Java

• ``````public class Solution {
//ab % k = (a%k)(b%k)%k,
//a^n % k = ((a % k)^n) % k, proof: induction, a^10 % k = (a^9 % k) * (a % k) % k = (((a % k)^9) % k) * (a % k) % k  = ((a % k)^10) % k

//(a^12345) % k = ((a^12340) * (a^5)) % k = (((a^1234)^10) * (a^5)) % k = ((((a^1234 % k)^10) % k) * ((a^5) % k)) % k
//super(a, 12345) = powerMode((super(a,1234),10) * powerMode(a, 5) % k
public int superPow(int a, int[] b) {
if (b == null || b.length == 0) return 1;
if (a == 0) return 0;

return helper(a, b, b.length - 1, 1337);
}

public int helper(int a, int[] b, int index, int k) {
if (index == 0) return powerMode(a, b[index], k);
return (powerMode(helper(a, b, index - 1, k),10, k)*powerMode(a, b[index], k)) % k;
}

//a^b % 1337,
//use: ab % k = ((a%k)*(b%k))%k,
public int powerMode(int a ,int b, int k) {
if (b == 0 || b == 1) return b == 0 ? 1 : a % k;

return (powerMode(a, b - 1, k)*(a % k)) % k;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.