Recursive Function to Multiply Two Positive Numbers

Aim

Write a program to multiply two positive numbers using recursion in Python.

• Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.
• Multiplying two numbers using recursion involves breaking down the multiplication process into smaller steps until a base case is reached.

Algorithm

1. Start
2. Define a recursive function multiply to multiply two positive numbers:
   • If the second number is 0, return 0 (base case).
   • Otherwise, return the first number plus the result of multiplying the first number and the second number minus 1 (recursive case).
3. Take input from the user:
   • Ask the user to enter two positive integers a and b.
4. Calculate the product of the two numbers:
   • Call the multiply function with a and b as arguments and store the result.
5. Print the result:
   • Display the product of the two numbers.
6. End

Program

# Define a recursive function to multiply two positive numbers
def multiply(a, b):
    if b == 0:
        return 0
    else:
        return a + multiply(a, b - 1)
 
# Take input from the user
a = int(input("Enter the first positive integer: "))
b = int(input("Enter the second positive integer: "))
 
# Calculate the product of the two numbers
result = multiply(a, b)
 
# Print the result
print(f"The product of {a} and {b} is {result}")

Sample Input/Output

Enter the first positive integer: 5
Enter the second positive integer: 3
The product of 5 and 3 is 15

Explanation

• We define a recursive function multiply to multiply two positive numbers:

  • If the second number b is 0, the function returns 0 because multiplying any number by 0 results in 0.
  • Otherwise, the function returns a plus the result of multiplying a and b-1, which is the recursive call.

• Let's break down the execution of the recursive function with an example:

  • Suppose the user enters 5 and 3.
  • The function call multiply(5, 3) will execute as follows:
    1. multiply(5, 3):
       • Since 3 is not 0, it returns 5 + multiply(5, 2).
    2. multiply(5, 2):
       • Since 2 is not 0, it returns 5 + multiply(5, 1).
    3. multiply(5, 1):
       • Since 1 is not 0, it returns 5 + multiply(5, 0).
    4. multiply(5, 0):
       • Since 0 is 0, it returns 0.

• Now, let's substitute back the values:

  • multiply(5, 0) returns 0.
  • multiply(5, 1) returns 5 + 0 = 5.
  • multiply(5, 2) returns 5 + 5 = 10.
  • multiply(5, 3) returns 5 + 10 = 15.

• Therefore, the product of 5 and 3 is 15.

• We take two input numbers a and b from the user and store them in the variables a and b.

• We calculate the product of a and b by calling the multiply function with a and b as arguments and store the result in the variable result.

• We print the result using the statement print(f"The product of {a} and {b} is {result}").

Complexity Analysis

• The time complexity of the recursive multiplication function is O(b) because it makes b recursive calls.
• The space complexity of the recursive multiplication function is O(b) because it uses the call stack to store b recursive calls.

How can you improve this program?

• You can add error handling to ensure the user enters positive integers.
• You can implement an iterative version of the multiplication function to avoid the overhead of recursive calls.

Summary

In this tutorial, we learned how to multiply two positive numbers using recursion in Python. We discussed the algorithm, program, and sample input/output for multiplying two numbers. We also analyzed the complexity of the recursive multiplication function and suggested possible improvements.