# Recursion

Recursive functions are functions that call themselves inside the function. As a computer programming technique, this is called Divide and Conquer and is key to the design of many important algorithms.

Recursion vs. Loops

Recursion and loops are equivalent structures. That is, any task you can achieve with one you can achieve with the other.

Recursion is most useful when you can break up your task into smaller subtasks.

You don’t need to see the whole process. Break it down into subproblems.

- Think base case
- What is the next case and relationships between those cases?

Use in Depth-First Search. However, I ran into Depth-First Search. However, I ran into Segmentation Fault. Recursion can go deep **about 512K** times.

### Iterative vs. Recursive Algorithms

Neither of the approach is intrinsically better than the other, really depends on the use case.

- Recursive solutions work really well for many data structures, such as Binary Search Trees
- Iterative solutions are sometimes simpler and more efficient
- Ex: For Fibonacci problem, you should use Dynamic Programming where iterative solution is $O(n)$, recursive solution (without Memoization) is ~$O(2_{n})$