Recursive Function to Add Two Positive Numbers

Aim

Write a program to add 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.
• Adding two numbers using recursion involves breaking down the addition process into smaller steps until a base case is reached.

Algorithm

1. Start
2. Define a recursive function add to add two positive numbers:
   • If the second number is 0, return the first number (base case).
   • Otherwise, return 1 plus the result of adding 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 sum of the two numbers:
   • Call the add function with a and b as arguments and store the result.
5. Print the result:
   • Display the sum of the two numbers.
6. End

Program

# Define a recursive function to add two positive numbers
def add(a, b):
    if b == 0:
        return a
    else:
        return 1 + add(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 sum of the two numbers
result = add(a, b)
 
# Print the result
print(f"The sum of {a} and {b} is {result}")

Sample Input/Output

Enter the first positive integer: 5
Enter the second positive integer: 3
The sum of 5 and 3 is 8

Explanation

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

  • If the second number b is 0, the function returns the first number a because adding 0 to any number results in the number itself.
  • Otherwise, the function returns 1 plus the result of adding 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 add(5, 3) will execute as follows:
    1. add(5, 3):
       • Since 3 is not 0, it returns 1 + add(5, 2).
    2. add(5, 2):
       • Since 2 is not 0, it returns 1 + add(5, 1).
    3. add(5, 1):
       • Since 1 is not 0, it returns 1 + add(5, 0).
    4. add(5, 0):
       • Since 0 is 0, it returns 5.

• Now, let's substitute back the values:

  • add(5, 0) returns 5.
  • add(5, 1) returns 1 + 5 = 6.
  • add(5, 2) returns 1 + 6 = 7.
  • add(5, 3) returns 1 + 7 = 8.

• Therefore, the sum of 5 and 3 is 8.

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

• We calculate the sum of a and b by calling the add 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 sum of {a} and {b} is {result}").

Complexity Analysis

• The time complexity of the recursive addition function is O(b) because it makes b recursive calls.
• The space complexity of the recursive addition 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 addition function to avoid the overhead of recursive calls.

Summary

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