Recursive Multiply

Write a recursive function to multiply two positive integers without using the * operator. You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

Solution

This problem is a great introductory problem for recursion. Let’s say we are multiplying two numbers, a * b. The base case is simple - when a = 1, we will return b. When a > 0, we will recurse, adding b all the way up the recursion tree. The depth of the recursion tree is a.

def recursive_multiply(a, b):
  if(a == 1):
    return b

  return b + recursive_multiply(a-1, b)