Basic Problems On Recursion In C++

 Below are 10 basic practice problems on recursion in C++ along with their solutions, outputs, and time and space complexity analysis

  1. 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:

csharp
Factorial of 5 is: 120

Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)

  1. 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:

csharp
The 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)

  1. 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:

c
Sum of array elements is: 15

Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)

  1. 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:

vbnet
2 raised to the power 5 is: 32

Time Complexity: O(exponent) Space Complexity: O(exponent) (due to the recursion stack)

  1. 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:

csharp
radar is a palindrome.

Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)

  1. 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:

csharp
Length of the linked list is: 5

Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)

  1. 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:

c
The number of occurrences of 2 in the array is: 3

Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)

  1. 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:

css
Printing numbers from 1 to 5: 1 2 3 4 5

Time Complexity: O(n) Space Complexity: O(n) (due to the recursion stack)

  1. 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:

mathematica
Element 6 found at index 2

Time Complexity: O(log n) Space Complexity: O(log n) (due to the recursion stack)

  1. 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:

css
Move 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

Post a Comment