# Recursion

## `Q1:`   <mark style="color:blue;">Head-Recursion</mark>

```cpp
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:`   <mark style="color:blue;">Tail-Recursion</mark>

```cpp

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](https://leetcode.com/problems/fibonacci-number/)

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

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2Fv7VblnjbvIg6lgF5IQJN%2Fimage.png?alt=media&#x26;token=7e7bda2d-d47e-4dc0-8715-309395baaa8f" alt=""><figcaption></figcaption></figure>

## `Q4:`   [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) --> <mark style="color:red;">TLE Error</mark>

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

## `Q5:`   <mark style="color:blue;">SayDigits</mark>

```cpp
#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:`    <mark style="color:blue;">isSorted-Array</mark>

```cpp
#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);
}
```

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FH8DEcVbEr9fo3ZSuzbzI%2FisSorted.jpg?alt=media&#x26;token=ff81b66a-79d2-4bf9-ba20-c00ef63f1d77" alt=""><figcaption></figcaption></figure>

## `Q7:`   [Check if Array Is Sorted and Rotated](https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/) > <mark style="color:red;">Pending</mark> <

## [Working Approach ](https://dsa-cpp.gitbook.io/nafees/arrays/1-d-array#q5-check-if-array-is-sorted-and-rotated)

```cpp

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

```cpp
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](https://www.codingninjas.com/studio/problems/reverse-the-string_799927) &#x20;

```cpp
#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)** ](https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation)[1](https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation).

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)** ](https://stackoverflow.com/questions/4326634/complexity-for-recursive-functions-time-and-space)[2](https://stackoverflow.com/questions/4326634/complexity-for-recursive-functions-time-and-space).

## `Q10:` <mark style="color:blue;">Find Exponent in logarithmic time</mark>

{% code title="TC: log n (log base 2 of n)    " %}

```cpp
#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);
}
```

{% endcode %}