# CLEAN CODE MODULAR EXPRESSION: BACKTRACKING | RECURSION

By: Saurav

2018-02-23 01:12:00 UTC

Implement pow(A, B) % C.

In other words, given A, B and C, find (AB)%C.

This is a nice case of recursion. But it's better to invest some time in it.

Algo:

If a is 0 -> return 0
if b is 0 -> return 1%c

Otherwise, write the base case of b == 1 and two recursive cases of odd and even b. We could have written simple case of b-1 and 1 but, in even case we can even enhance the solution by dividing b in to b/2 and b/2 in the recursion tree as shown in the code. Lets write the tests first

```p mod(0,0,3)  == 0
p mod(1,0,3) == 1
p mod(3,3,3) == 0
```

```def mod(a, b, c)
return 0 if a == 0

return 1%c if b == 0

if b <= 1
return a%c
else
if b%2 == 0
r = mod(a, b/2, c)
return ( r* r)%c
else
return (a%c * mod(a, b-1, c))%c
end
end

end```

### Let me know what you think! twitter: sprakash24octlinkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :) 