Below are 10 basic practice problems on recursion in C++ along with their solutions, outputs, and time and space complexity analysis
- 1)Factorial:
cpp#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 0 || n == 1)
return 1;
return n * factorial(n - 1);
}
int main() {
int n = 5;
cout << "Factorial of " << n << " is: " << factorial(n) << endl;
return 0;
}
Output:
csharpFactorial of 5 is: 120
Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)
- Fibonacci Sequence:
cpp#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 6;
cout << "The " << n << "th number in the Fibonacci sequence is: " << fibonacci(n) << endl;
return 0;
}
Output:
csharpThe 6th number in the Fibonacci sequence is: 8
Time Complexity: O(2^n) (inefficient due to redundant calculations) Space Complexity: O(n) (due to the recursion stack)
- 2)Sum of Array Elements:
cpp#include <iostream>
using namespace std;
int arraySum(int arr[], int n) {
if (n <= 0)
return 0;
return arr[n - 1] + arraySum(arr, n - 1);
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum of array elements is: " << arraySum(arr, n) << endl;
return 0;
}
Output:
cSum of array elements is: 15
Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)
- 3)Power Function:
cpp#include <iostream>
using namespace std;
int power(int base, int exponent) {
if (exponent == 0)
return 1;
return base * power(base, exponent - 1);
}
int main() {
int base = 2, exponent = 5;
cout << base << " raised to the power " << exponent << " is: " << power(base, exponent) << endl;
return 0;
}
Output:
vbnet2 raised to the power 5 is: 32
Time Complexity: O(exponent) Space Complexity: O(exponent) (due to the recursion stack)
- 4)Palindrome Check:
cpp#include <iostream>
using namespace std;
bool isPalindrome(string str, int start, int end) {
if (start >= end)
return true;
return (str[start] == str[end]) && isPalindrome(str, start + 1, end - 1);
}
int main() {
string str = "radar";
if (isPalindrome(str, 0, str.length() - 1))
cout << str << " is a palindrome." << endl;
else
cout << str << " is not a palindrome." << endl;
return 0;
}
Output:
csharpradar is a palindrome.
Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)
- 5)Recursive List Length:
cpp#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int listLength(Node* head) {
if (head == nullptr)
return 0;
return 1 + listLength(head->next);
}
int main() {
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};
head->next->next->next = new Node{4, nullptr};
head->next->next->next->next = new Node{5, nullptr};
cout << "Length of the linked list is: " << listLength(head) << endl;
// Clean up memory (not essential for the problem but good practice)
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
return 0;
}
Output:
csharpLength of the linked list is: 5
Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)
- 6)Count Occurrences:
cpp#include <iostream>
using namespace std;
int countOccurrences(int arr[], int n, int key) {
if (n == 0)
return 0;
return (arr[n - 1] == key) + countOccurrences(arr, n - 1, key);
}
int main() {
int arr[] = {2, 3, 2, 4, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 2;
cout << "The number of occurrences of " << key << " in the array is: " << countOccurrences(arr, n, key) << endl;
return 0;
}
Output:
cThe number of occurrences of 2 in the array is: 3
Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)
- 7)Print Numbers:
cpp#include <iostream>
using namespace std;
void printNumbers(int n) {
if (n <= 0)
return;
printNumbers(n - 1);
cout << n << " ";
}
int main() {
int n = 5;
cout << "Printing numbers from 1 to " << n << ": ";
printNumbers(n);
cout << endl;
return 0;
}
Output:
cssPrinting numbers from 1 to 5: 1 2 3 4 5
Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)
- 8)Binary Search:
cpp#include <iostream>
using namespace std;
int binarySearch(int arr[], int low, int high, int key) {
if (low > high)
return -1;
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
else
return binarySearch(arr, mid + 1, high, key);
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12, 14};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 6;
int index = binarySearch(arr, 0, n - 1, key);
if (index != -1)
cout << "Element " << key << " found at index " << index << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}
Output:
mathematicaElement 6 found at index 2
Time Complexity: O(log n) Space Complexity: O(log n) (due to the recursion stack)
- 9)Tower of Hanoi:
cpp#include <iostream>
using namespace std;
void towerOfHanoi(int n, char source, char auxiliary, char destination) {
if (n == 1) {
cout << "Move disk 1 from " << source << " to " << destination << endl;
return;
}
towerOfHanoi(n - 1, source, destination, auxiliary);
cout << "Move disk " << n << " from " << source << " to " << destination << endl;
towerOfHanoi(n - 1, auxiliary, source, destination);
}
int main() {
int n = 3;
towerOfHanoi(n, 'A', 'B', 'C');
return 0;
}
Output:
cssMove disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Time Complexity: O(2^n) (number of moves) Space Complexity: O(n) (due to the recursion stack)
These practice problems cover a variety of scenarios where recursion can be applied. Remember that recursion can be less efficient than iterative approaches in some cases, so understanding when to use recursion is crucial.
Hope these problems help you to make your basics more strong we will update this blog post as we get more problems.Happy Coding !
Comments