How to use Recursion In C++
Algorithm
// Base case: If A is greater than 0, then return B if(A > 0) return B; // Update A to (A&B)<<1 and B to A ^ B and recursively call for the updated value else recursive_function((A & B) << 1, A ^ B);
C++ Program to Add Two Numbers Using Recursion
C++
// C++ program to add two number // using Recursion #include <iostream> // Function to return sum // of two number int addTwoNumber(int A, int B) { // Base Case if (!A) return B; // Recursive Call else return addTwoNumber((A & B) << 1, A ^ B); } // Driver Code int main() { // Given two number int A = 4, B = 11; // Function call printf("sum = %d", addTwoNumber(A, B)); return 0; } |
Output
sum = 15
- Time complexity: O(log n)
- Auxiliary Space: O(log n)
Explanation
- (A & B) << 1: This expression calculates the bitwise AND of A and B and then left-shifts the result by one position. This is done to carry over the bits that are set in both A and B.
- A ^ B: This expression calculates the bitwise XOR of A and B. This is done to perform the addition without carrying.
- The recursive call addTwoNumber((A & B) << 1, A ^ B); keeps adding the numbers until A becomes zero (base case). At each recursive step, the function calculates the carry bits and the non-carry bits separately and recursively calls itself with the new values.
Add Two Numbers in C++
The addition of two numbers is a simple task in C++ that can be done using the arithmetic addition operator (+). But there are many other ways to find the sum of two numbers in C++. In this article, we will discuss 7 different ways to add two numbers in C++.