# Recursion

### Recursion

Recursion is a process in which a function calls itself directly or indirectly. It’s a technique used to solve problems by breaking them down into smaller, more manageable sub-problems. A recursive function must have a base case or stopping criteria to avoid infinite recursion.

#### Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

#### Examples

**The Factorial**

In mathematics, the factorial of a non-negative integer, denoted by `n!`, is the product of all positive integers less than or equal to `n`. For example, the factorial of `3` represents the multiplication of numbers `3, 2, 1`, i.e `3! = 3 × 2 × 1` and is equal to `6`.

Let's implement it with recursion:

```csharp
 
    Console.WriteLine(Factorial(3));

public partial class Program 
{

    public static int Factorial(int number)
    {
        if (number < 1)
        {
            return 1;
        }

        return number * Factorial(number - 1);

    }
}

```

> Complexity

* **Time complexity**: `O(N)`
* **Space complexity**: `O(1)`

**The Fibonacci series**

In the Fibonacci series, each number is the sum of the two preceding ones. For an example: `0,1,1,2,3,5,8,13,21`.

Let's implement it with recursion:

```csharp

for (int i = 0; i < 5; i++)
{
    Console.WriteLine(Fibonacci(i));
}



public partial class Program 
{
    public static int Fibonacci(int number)
    {

        if (number < 2)
        {
            return number;
        }

        return Fibonacci(number - 1) + Fibonacci(number - 2);
    }
}

```

> Complexity

* **Time complexity**: `O(2^N)`
* **Space complexity**: `O(1)`

As we know,  `O(2^N)` time complexity is not good as per performance prospactive. Can we improve it? Yes, we can with the help of dynamic programming (Memoization/Caching). For an example:

```csharp
for (int i = 0; i < 10; i++)
{
    Console.WriteLine(Fibonacci(i));
}



public partial class Program 
{
    private static Dictionary<int, int> fibonacci = new();
    public static int Fibonacci(int number)
    {
        if (number < 2)
        {
            return number;
        }

        // check result in cache
        if (fibonacci.ContainsKey(number))
        {
            return fibonacci[number];
        }

        var result =  Fibonacci(number - 1) + Fibonacci(number - 2);
        fibonacci[number] = result;
        return result;
    }
}

```

> Complexity

* **Time complexity**: `O(N)`. This is because the function only computes each Fibonacci number once due to memoization.
* **Space complexity**: `O(N)`. This is because the algorithm uses a dictionary to store the Fibonacci numbers, and the size of this dictionary grows linearly with `n`, the number of numbers generated.

> NOTE: Always cache repetitive steps data.


---

# Agent Instructions: 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://docs-57.gitbook.io/data-structure-and-algorithms/algorithms/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.