> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/recursion.md).

# 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="/files/p4nbDTTzFel65kxPsGZN" 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="/files/HfaQm9Rh12heZE9EJSFi" 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 ](/nafees/arrays/1-d-array.md#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 %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/recursion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.