☠️Recursion

Q1: Head-Recursion

void headRecursion(int count) {
    
    // Base-Condition
    if (count == 0)
        return;

    // Recursive Relation
    headRecursion(count - 1);
    
    // Processing
    cout << count << " ";
}

// o/p = 1 2 3 4 5

Q2: Tail-Recursion

void tailRecursion(int count) {
    // Base-Condition
    if (count == 0)
        return;
   
    // Processing
    cout << count << " ";
    
    // Recursive Relation
    tailRecursion(count - 1); 
}

// o/p = 5 4 3 2 1

Q3: Fibonacci Number

int fib(int n) {
    if(n < 2)
        return n;
    return fib(n-1) + fib(n-2);
}

Q4: Climbing Stairs --> TLE Error

int climbStairs(int n) {
    if(n < 0) 
        return 0;
    if(n == 0) 
        return 1;
            
    return climbStairs(n-1) + climbStairs(n-2);
}

Q5: SayDigits

#include <iostream>
using namespace std;

void sayDigits(int x, string* arr) {
    if (x == 0) return ;

    int digit = x%10;
    x /= 10;
    sayDigits(x, arr);

    cout << arr[digit] << " ";
}

int main() {
    string arr[] =  {"Zero", "One", "Two", "Three", "Four", 
                        "Five", "Six", "Seven", "Eight", "Nine"};
    sayDigits(4129192, arr);
}

Q6: isSorted-Array

#include <iostream>
using namespace std;

bool isSorted(int *arr, int size, int i = 0) {
    if(i == size-1) return true;

    if(arr[i] > arr[i+1]) return false;

    isSorted(arr, size, ++i);
}

int main() {
    int arr[4] = {5, 7, 7, 10};
    cout << boolalpha << isSorted(arr, 4);
}

Q7: Check if Array Is Sorted and Rotated > Pending <

Working Approach

bool isSorted(int arr[], int size);
bool isRotated(int arr[], int size);

bool check(int nums[], int size) {

    return isSorted(nums, size);
}

bool isSorted(int arr[], int size) {
    if(size == 0 || size == 1) 
        return true;

    if(arr[0] > arr[1])
        return isRotated(arr + 1, size);
    
    return isSorted(arr + 1, size - 1);
}

bool isRotated(int arr[], int size) {
    if(size == 0 || size == 1) 
        return true;

    if(arr[0] > arr[1])
        return false;
    
    return isRotated(arr + 1, size - 1);
}

int main() {
    int arr[5] = {3,4,5,1,2};

    if(check(arr, 5))
        cout << "Given Array is Sorted or Rotated";
    else
        cout << "Given Array isn't Sorted or Rotated";
}

Q8: Linear Search

void print(int arr[], int size) {
    cout << "Size: " << size << endl;

    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    } cout << endl;
}

bool linearSearch(int arr[], int size, int k) {
    print(arr, size);
    
    if(size == 0)
        return false;
    if(arr[0] == k)
        return true;
    
    return linearSearch(arr + 1, size - 1, k);
}

Day-04 Recursion

Q9: Reverse String

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

void reverseString(char* str, int e, int s = 0) {
    if(s > e) return ;
    
    swap(str[s], str[e]);

    reverseString(str, --e, ++s);
}

int main() {
    char str[] = "nafees";
    reverseString(str, strlen(str)-1);
    for (auto c : str) {
        cout << c << " ";
    }
}

In this program, the recursiveFunc() function is called recursively until the base case is reached. The base case is when s > e. Therefore, the number of recursive calls made by the function is equal to half the length of the string. Hence, the time complexity of your program is O(n/2) or O(n) 1.

The space complexity of your program depends on the maximum depth of recursion. In your program, the maximum depth of recursion is equal to half the length of the string. Therefore, the space complexity of your program is O(n/2) or O(n) 2.

Q10: Find Exponent in logarithmic time

TC: log n (log base 2 of n)

#include "iostream"
using namespace std;

int findExpo(int a, int pow, int ans = 0) {
     
     if(pow == 0) return 1;
     
     else if(pow == 1) return a;
     
     
     else if(pow % 2 == 0) {
     // a^(n/2).a^(n/2)
          ans = findExpo(a, pow/2, ans);
          return ans * ans;
     }
     else {
     // a^[(n-1)/2].a^[(n-1)/2].a
          ans = findExpo(a, (pow-1)/2, ans);
          return ans*ans*a;
     }
}

int main() {
     int a = 2,pow = 7;

     cout <<  findExpo(a, pow);
}