Modulus

In this lesson, we will learn about the modulo operation and how to implement it using recursion.

We'll cover the following

What is the modulo operation?

The modulo operation (abbreviated as mod) returns the remainder when a number is divided by another. The symbol for mod is %.

The number being divided is called the dividend, and the number that divides is called the divisor.

The illustration below represents the concept of remainders using basic division example:

Mathematical Notation

The above illustration can be mapped on to the following equation:

4∗3+2=144 * 3 + 2 = 14

Generically, (divisor∗quotient)+remainder=dividend(divisor * quotient) + remainder = dividend

Implementation

Let’s have a look at the code:

Press + to interact
def mod(dividend, divisor) :
  # Check division by 0
  if divisor == 0 :
    print("Divisor cannot be ")
    return 0
  # Base Case
  if dividend < divisor :
    return dividend
  # Recursive Case
  else :
    return mod(dividend - divisor, divisor)
# Driver Code
print(mod(10, 4))

Explanation:

Let’s discuss how we reached this solution. Look at the illustration below. It shows that if a number is divided by 44, it can give 44 remainders: 00, 11, 22, and 33.

widget

Notice that the remainder repeats after every 44 iteration. This means:

10mod4=6mod4=2mod410 \: mod \: 4 = 6 \: mod \: 4 = 2 \: mod \: 4

10mod4=(10−4)mod4=(10−4−4)mod410 \: mod \: 4 = (10-4) \: mod \: 4 = (10-4-4) \: mod \: 4

We can then generalize this as follows:

dividendmoddivisordividend \: mod \: divisor

⇒(dividend−divisor)moddivisor\Rightarrow (dividend-divisor) \: mod \: divisor

⇒(dividend−divisor−divisor)moddivisor\Rightarrow(dividend-divisor-divisor) \: mod \: divisor

⇒...\Rightarrow ...

We can continue subtracting divisordivisor from dividenddividend until the dividenddividend becomes less than divisordivisor. In this case, the remainder will be the dividenddividend

This mathematical generalization

dividendmoddivisor=(dividend−divisor)moddivisordividend \: mod \: divisor = (dividend-divisor) \: mod \: divisor

will be our recursive case, while the condition when the dividenddividend is less than the divisordivisor will be our base case.

Let’s have a look at the sequence of function calls being made:

In the next lesson, we have a problem for you to solve.