<aside> 💡 What is a Recursion?

A way of solving a problem by having a function calling itself.

It performs same operations multiple times with different inputs.

In every step we try smaller inputs to make Problem smaller.

Base condition should be mandatory. because, it stops recursion from entering into infinite loop.

Ex: factorial, Fibonacci.

#factoriel program.
def factorial(n):
    if n == 0:  # Base case
        return 1
    else:  # Recursive case
        return n * factorial(n - 1)

</aside>

<aside> 💡 Why recursion?

It help us break down big problems into smaller ones and easier to use.

For example, sort, search, and traversal problems

It simplifies the code and improve readability.

It is used in many algorithms like, divide and conquer, greedy and dynamic Programming.

It as a major prominent major usage in data structures like trees and graphs.

</aside>

<aside> 💡 How does recursion works?

Recursion works by breaking down a complex problem into simpler, smaller instances of the same problem.

</aside>

<aside> 💡 General Steps of how Recursion Works?

Step1. Identify the base : The base case is the simplest form of the problem that can be directly solved without further recursion. it helps in terminating the condition for the recursive calls.

Step2. Define the recursive Case: this defines how the problem can be divided into smaller sub-problems. it identifies the relationship between the problem and smaller instances of the same Problem. this step also involves of calling the function itself with the modified Output.

Step3. Make Progress towards the Base Case.

Step4. Return the values and Combine the results

Step5. Propagate the Results

</aside>

<aside> 💡 When to Use Recursion?

1. Problems with recursive structures: Recursive data structures, such as trees or graphs, are often well-suited for recursive algorithms.

2. Divide-and-conquer algorithms: Problems that can be divided into smaller subproblems, solved independently, and then combined to obtain the final result are often solved using recursion. Ex: 1. quicksort and merge sort, rely on recursive calls to handle the subproblems.

3. Permutations and combinations: Problems involving permutations and combinations can be effectively solved using recursion.

4. Dynamic programming: Dynamic programming is a technique that involves solving complex problems by breaking them down into overlapping subproblems and storing the results to avoid redundant computations. Recursion is often used in dynamic programming to solve these subproblems recursively.

5. Mathematical and combinatorial problems: Many mathematical problems, such as calculating the Fibonacci sequence or solving the Tower of Hanoi puzzle, have recursive definitions that lend themselves naturally to recursive solutions.

6. Problems with a self-similar structure: Recursive solutions are often suitable for problems with a self-similar structure. For example, fractals, such as the Mandelbrot set or the Sierpinski triangle, can be generated using recursive algorithms

</aside>

<aside> 💡 Differences between recursive and Iterative Approaches?

Recursion

• Terminates when a base case is reached.
• Each recursive call requires extra space on the stack frame (memory).
• If we get infinite recursion, the program may run out of memory and result in stack overflow.
• Solutions to some problems are easier to formulate recursively.

Iteration

• Terminates when a condition is proven to be false.
• Each iteration does not require extra space.
• An infinite loop could loop forever since there is no extra memory being created.
• Iterative solutions to a problem may not always be as obvious as a recursive solution. </aside>

<aside> 💡 How to write a recursion in three steps effectively for any given problem?

When approaching a problem using recursion, you can follow a general three-step process to design an effective recursive solution. These steps help in breaking down the problem, defining the base case, and formulating the recursive case.

1.Identify the cases, recursive case, base case.

2.Define the recursive case which should terminate at the base case.

3.Make progress towards the base case

#Fibonacci Sequence: it's a sequence of number in which each number is sum of its preceding numbers.
#Note: Sequence tarts from 0 and 1.
#EX: 0,1,1,2,3,5,8,13,21,34,55,89.....so-on.

def Fibonacci(n):
		#UNINTENTIONAL CASE - CONSTRAINTS
			assert n>=0 and int(n) == n, "Fibonacci number cannot be negative number or non integer."
		#2nd Identify the BaseCase
			if n in [0,1]:
					return n
			else:
		#1st Indentify the recursive case
					return Fibonacci(n-1)+fibonacci(n-2)

</aside>

<aside> 💡 Example Algorithms of Recursion:

• Fibonacci series, factorial finding
• Merge sort, quick sort
• Binary search
• Tree traversals and many tree problems: InOrder, PreOrder PostOrder
• Graph traversals: DFS [Depth First Search] and BFS [Breadth First Search]
• Dynamic programming examples
• Divide and conquer algorithms
• Towers of Hanoi Backtracking algorithms </aside>

<aside> 💡 How to measure recursion functions that make multiple calls?

When measuring the performance of a recursive function that involves multiple recursive calls, you can use various metrics to analyze its efficiency. Here are a few approaches to measure and analyze the performance of such recursive functions:

1. Execution time: Measure the total time taken by the recursive function to execute. You can use built-in timers or libraries specific to the programming language you're using to calculate the elapsed time. By comparing the execution time for different input sizes, you can evaluate the function's efficiency and understand how it scales.
2. Recursive call count: Track the number of recursive calls made by the function. This metric helps you understand how many times the function is being invoked and can provide insights into the function's complexity. Too many recursive calls can indicate potential performance issues or the need for optimization.
3. Stack depth: Recursive function calls utilize the call stack, and each recursive call adds a new frame to the stack. By measuring the maximum stack depth reached during the execution of the recursive function, you can evaluate its memory usage and potential stack overflow risks. Excessive stack depth can lead to performance issues and may require tail recursion optimization or an iterative alternative.
4. Input size and recursion depth relationship: Analyze the relationship between the input size and the depth of recursion. By varying the input size and observing how the recursion depth changes, you can understand how the function scales with different input sizes. This analysis can help identify potential performance bottlenecks or areas for optimization.
5. Space complexity: Evaluate the space complexity of the recursive function. Recursive functions typically consume additional memory due to the call stack frames. By analyzing the memory usage and how it grows with input size, you can estimate the space complexity and determine if it is acceptable for your requirements. </aside>

Recursion Problems