Recursion, Design and Analysis of Algorithms

Basics of Recursion

Definition and Concept of Recursion

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. The main idea is to break down a complex problem into simpler sub-problems that are easier to solve. Each recursive call solves a smaller instance of the original problem.

Components of a Recursive Function

A recursive function typically has two main components:

1. Base Case: This is the condition under which the recursion stops. Without a base case, the function would call itself indefinitely, leading to a stack overflow error.
2. Recursive Case: This is the part of the function where it calls itself with a smaller or simpler input.

How Recursion Works

When a recursive function is called, it performs the following steps:

1. Check if the base case is met. If yes, return the result.
2. If the base case is not met, perform some operations and call the function itself with modified arguments.
3. Each call adds a new frame to the call stack, which is a data structure that stores information about the active subroutines or functions in a program.
4. When the base case is reached, the function returns, and the call stack starts to unwind, resolving each recursive call.

Simple Examples

1. Factorial Calculation The factorial of a non-negative integer ( n ) is the product of all positive integers less than or equal to ( n ). It is denoted as ( n! ).

   int factorial(int n) {
       if (n == 0) {
           return 1;  // Base case: 0! = 1
       } else {
           return n * factorial(n - 1);  // Recursive case
       }

Example:

   #include <iostream>
   using namespace std;

   int factorial(int n);

   int main() {
       cout << factorial(5) << endl;  // Output: 120
       return 0;
   }

1. Fibonacci Sequence The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

   int fibonacci(int n) {
       if (n <= 1) {
           return n;  // Base case: fibonacci(0) = 0, fibonacci(1) = 1
       } else {
           return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive case
       }
   }

Example:

   #include <iostream>
   using namespace std;

   int fibonacci(int n);

   int main() {
       cout << fibonacci(5) << endl;  // Output: 5
       return 0;
   }

Advantages of Recursion

• Simplicity: Recursive solutions are often more elegant and easier to understand.
• Natural Fit for Certain Problems: Problems involving trees, graphs, and other hierarchical structures are naturally suited for recursion.

Disadvantages of Recursion

• Performance: Recursive solutions can be less efficient due to the overhead of multiple function calls and stack usage.
• Memory Usage: Each recursive call consumes stack space, which can lead to stack overflow if the recursion depth is too large.
• Complexity in Debugging: Recursive functions can be more difficult to debug and trace, especially for complex problems.

Recursion vs Iteration

• Iteration: Uses loops (for, while) to repeat a block of code until a condition is met. It is generally more efficient in terms of memory and performance.
• Recursion: More intuitive and easier to implement for problems that can be divided into similar sub-problems.

Aspect	Recursion	Iteration
Approach	Function calls itself	Loop repeats a block of code
Memory Usage	Uses stack memory	Uses constant memory
Performance	Can be slower due to overhead	Generally faster
Complexity	Can be more elegant and intuitive	May require more complex code
Use Cases	Problems with hierarchical data	Problems with repetitive tasks

When to Use Recursion

• When the problem can be divided into similar sub-problems.
• When the problem involves tree or graph structures.
• When the iterative solution is too complex to implement.

Example for Recursive Functions

Recursive functions in programming are functions that call themselves directly or indirectly to solve a problem. This technique breaks down complex problems into simpler subproblems, handling each subproblem independently until the base case is reached. Recursive functions are essential in tasks like traversing data structures, generating sequences, and solving certain types of mathematical problems.

Check if Array is Increasing

A recursive approach to check if an array is strictly increasing involves comparing each element with the next in the array until the end is reached. Here's an implementation in C++:

#include <iostream>
using namespace std;

// Recursive function to check if the array is strictly increasing
bool isIncreasing(int arr[], int size, int currentIndex = 0) {
    // Base case: If currentIndex reaches size - 1, the entire array is checked
    if (currentIndex == size - 1) {
        return true;
    }

    // Recursive call: Check if current element is less than the next element
    if (arr[currentIndex] < arr[currentIndex + 1]) {
        return isIncreasing(arr, size, currentIndex + 1);
    } else {
        return false;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};      // Example increasing array
    int size = sizeof(arr) / sizeof(arr[0]);

    if (isIncreasing(arr, size)) {
        cout << "The array is strictly increasing." << endl;
    } else {
        cout << "The array is not strictly increasing." << endl;
    }

    return 0;
}

Check if Array is Decreasing

Similarly, to check if an array is strictly decreasing using recursion, you compare each element with the next in reverse order until the start of the array is reached:

#include <iostream>
using namespace std;

// Recursive function to check if the array is strictly decreasing
bool isDecreasing(int arr[], int size, int currentIndex = 0) {
    // Base case: If currentIndex reaches size - 1, the entire array is checked
    if (currentIndex == size - 1) {
        return true;
    }

    // Recursive call: Check if current element is greater than the next element
    if (arr[currentIndex] > arr[currentIndex + 1]) {
        return isDecreasing(arr, size, currentIndex + 1);
    } else {
        return false;
    }
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};      // Example decreasing array
    int size = sizeof(arr) / sizeof(arr[0]);

    if (isDecreasing(arr, size)) {
        cout << "The array is strictly decreasing." << endl;
    } else {
        cout << "The array is not strictly decreasing." << endl;
    }

    return 0;
}

Find First Occurrence of an Element in an Array

A recursive approach to find the first occurrence of an element in an array involves comparing each element with the target element until the element is found or the end of the array is reached. Here's an implementation in C++:

#include <iostream>
using namespace std;

// Recursive function to find the first occurrence of a target in an array
int findFirstOccurrence(int arr[], int size, int target, int currentIndex = 0) {
    // Base case: If currentIndex reaches size, return -1 (target not found)
    if (currentIndex == size) {
        return -1;
    }

    // Check if current element equals target
    if (arr[currentIndex] == target) {
        return currentIndex;
    }

    // Recursive call to check the rest of the array
    return findFirstOccurrence(arr, size, target, currentIndex + 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 5, 2};  // Example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;

    int firstIndex = findFirstOccurrence(arr, size, target);

    if (firstIndex != -1) {
        cout << "The first occurrence of " << target << " is at index " << firstIndex << endl;
    } else {
        cout << target << " is not found in the array" << endl;
    }

    return 0;
}

Find Last Occurrence of an Element in an Array

A recursive approach to find the last occurrence of an element in an array involves comparing each element with the target element, starting from the last element and moving towards the first, until the element is found or the beginning of the array is reached. Here's an implementation in C++:

#include <iostream>
using namespace std;

// Recursive function to find the last occurrence of a target in an array
int findLastOccurrence(int arr[], int size, int target, int currentIndex = 0) {
    // Base case: If currentIndex reaches -1, return -1 (target not found)
    if (currentIndex == -1) {
        return -1;
    }

    // Check if current element equals target
    if (arr[currentIndex] == target) {
        return currentIndex;
    }

    // Recursive call to check the previous element
    return findLastOccurrence(arr, size, target, currentIndex - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 5, 2};  // Example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;

    int lastIndex = findLastOccurrence(arr, size, target, size - 1);

    if (lastIndex != -1) {
        cout << "The last occurrence of " << target << " is at index " << lastIndex << endl;
    } else {
        cout << target << " is not found in the array" << endl;
    }

    return 0;
}

Print All Occurrences of an Element in an Array

A recursive approach to print all occurrences of an element in an array involves comparing each element with the target element and printing the index whenever the element is found. The function continues to search through the array recursively until all occurrences are printed. Here's an implementation in C++:

#include <iostream>
using namespace std;

// Recursive function to print all occurrences of a target in an array
void printAllOccurrences(int arr[], int size, int target, int currentIndex = 0) {
    // Base case: If currentIndex reaches size, return (end of array)
    if (currentIndex == size) {
        return;
    }

    // Check if current element equals target
    if (arr[currentIndex] == target) {
        cout << "Found at index " << currentIndex << endl;
    }

    // Recursive call to check the next element
    printAllOccurrences(arr, size, target, currentIndex + 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 2, 5, 2};  // Example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 2;

    cout << "Occurrences of " << target << " in the array:" << endl;
    printAllOccurrences(arr, size, target);

    return 0;
}

Convert String to Number Using Recursion

Converting a string representation of a number into an integer using recursion in C++ involves processing each character of the string recursively, converting it to its numeric value, and accumulating the result. Here's how you can implement this, starting from the last character of the string:

#include <iostream>
#include <string>
using namespace std;

// Helper function to calculate the integer value of a character (digit)
int charToInt(char c) {
    return c - '0';
}

// Recursive function to convert string to integer starting from the last character
int stringToNumber(const string& str, int index) {
    // Base case: If index goes below 0, return 0
    if (index < 0) {
        return 0;
    }

    // Recursive call to process the previous character and multiply by 10
    int num = stringToNumber(str, index - 1);
    int digit = charToInt(str[index]);



    return num * 10 + digit;
}

int main() {
    string str = "12345"; // Example string representing a number
    int lastIndex = str.size() - 1;
    int number = stringToNumber(str, lastIndex);

    cout << "String \"" << str << "\" converted to number: " << number << endl;

    return 0;
}

Convert String to Reverse Number Using Recursion

To convert a string representation of a number into its reverse integer form using recursion in C++, you can recursively process each character of the string and accumulate the number in reverse order. Here's how you can implement this:

#include <iostream>
#include <string>
using namespace std;

// Recursive function to convert string to reverse number
int stringToReverseNumber(const string& str, int index = 0) {
    // Base case: If index reaches the end of the string, return 0
    if (index == str.size()) {
        return 0;
    }

    // Recursive call to process the next character and multiply by 10
    int num = stringToReverseNumber(str, index + 1);
    int digit = str[index] - '0';

    return num * 10 + digit;
}

int main() {
    string str = "12345"; // Example string representing a number
    int reversedNumber = stringToReverseNumber(str);

    cout << "String \"" << str << "\" converted to reverse number: " << reversedNumber << endl;

    return 0;
}

Tiling Problem for 4xN Grid

The problem involves tiling a 4xN grid using either 4x1 tiles or 1x4 tiles. We need to determine the number of ways to completely cover the grid using these tiles.

#include <iostream>
using namespace std;

// Recursive function to count the number of ways to tile a 4xN grid
int countWaysToTile(int n) {
    // Base cases
    if (n <= 0) {
        return 0;
    }
    if (n == 1 || n == 2 || n == 3) {
        return 1; // Only one way to tile for these cases using 4x1 tiles
    }
    if (n == 4) {
        return 2; // Two ways to tile a 4x4 grid (either four 1x4 tiles or sixteen 1x1 tiles)
    }

    // Recursive calls considering placing either a vertical 4x1 tile or a horizontal 1x4 tile
    return countWaysToTile(n - 1) + countWaysToTile(n - 4);
}

int main() {
    int n = 5; // Example grid size (4x5)
    int ways = countWaysToTile(n);

    cout << "Number of ways to tile a 4x" << n << " grid: " << ways << endl;

    return 0;
}

Climbing Stairs Problem with 1, 2, and 3 Steps

The climbing stairs problem involves determining the number of distinct ways to reach the top of a staircase of n steps. You can take steps of 1, 2, or 3 at a time. Here's a recursive approach to solve this problem in C++:

#include <iostream>
using namespace std;

// Recursive function to count the number of ways to climb stairs with 1, 2, or 3 steps
int climbStairs(int n) {
    // Base cases
    if (n == 0) {
        return 1; // Base case: One way to stay at ground level
    }
    if (n < 0) {
        return 0; // Base case: No ways to go below ground level
    }
    if (n == 1) {
        return 1; // Only one way to climb 1 step (take one 1-step)
    }

    // Recursive calls considering taking either 1, 2, or 3 steps
    return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3);
}

int main() {
    int n = 4; // Example number of steps
    int ways = climbStairs(n);

    cout << "Number of ways to climb " << n << " steps: " << ways << endl;

    return 0;
}

Generating Binary Strings with No Consecutive 1s

To solve the problem of generating binary strings of length n with no consecutive 1s using recursion in C++, we can implement the following approach:

#include <iostream>
using namespace std;

// Recursive function to count binary strings of length n with no consecutive 1s
int countBinaryStrings(int n, bool lastWasOne = false) {
    // Base case: If length is 0, return 1 (empty string)
    if (n == 0) {
        return 1;
    }

    // Initialize count
    int count = 0;

    // If last character was '1', current character can only be '0'
    if (lastWasOne) {
        count += countBinaryStrings(n - 1, false);
    }
    // If last character was '0', current character can be either '0' or '1'
    else {
        count += countBinaryStrings(n - 1, false); // Try appending '0'
        count += countBinaryStrings(n - 1, true);  // Try appending '1'
    }

    return count;
}

int main() {
    int n = 4; // Example length of binary strings
    int ways = countBinaryStrings(n);

    cout << "Number of binary strings of length " << n << " with no consecutive 1s: " << ways << endl;

    return 0;
}

Generating All Subsets/Subsequences of a String Using Recursion

To generate all subsets (subsequences) of a given string using recursion, you can implement a recursive function that includes or excludes each character of the string. Here’s how you can do this in C++:

Code:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Recursive function to generate all subsets/subsequences of a given string
void generateSubsets(const string& str, string current, int index, vector<string>& result) {
    // Base case: If index reaches the length of the string, add the current subset to the result
    if (index == str.size()) {
        result.push_back(current);
        return;
    }

    // Exclude the current character and recurse
    generateSubsets(str, current, index + 1, result);

    // Include the current character and recurse
    generateSubsets(str, current + str[index], index + 1, result);
}

int main() {
    string str = "abc"; // Example string
    vector<string> subsets;

    // Generate all subsets
    generateSubsets(str, "", 0, subsets);

    // Print all generated subsets
    cout << "All subsets of \"" << str << "\":" << endl;
    for (const string& subset : subsets) {
        cout << "\"" << subset << "\"" << endl;
    }

    return 0;
}