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

# Recursion

* Recursion is a Self-referential situation. In programming, recursion means calling a function in itself
* In general, most of the problems can be solved without recursion
* The recursive solutions are likely to be much cleaner and concise
* Decision on when to use recursion
  * For some problems, a recursive solution, though possible, will be awkward rather than elegant.
  * Recursive implementations **often consume more memory than non-recursive ones**.
  * In some cases, **using recursion may result in a slower execution time**

## Recursion in Python

### Namespace

* When we call a function in python, the **interpreter creates a new local namespace**, which avoids variable collision with the variables defined somewhere else in the code
* The interpreter also creates a separate local namespace for each instance of the function
* The recursion function in python has a limit (of 1000 calls) on the number of times it can call itself
* **Maintaining State**

  When dealing with recursive functions, keep in mind that each recursive call has its own execution context, so to maintain state during recursion you have to either:

  * Thread the state through each recursive call so that the current state is part of the current call’s execution context
  * Keep the state in the global scope

### Base Case

* The recursion function must have the following things
  * There are base cases that are directly solvable without the need for further recursion.
  * Each recursive call moves the solution progressively closer to a base case

### Call Stack

### Pros and Cons of Recursion

### Recursion vs Iteration

* Recursion results are in similar behavior to for or while loops
  * except recursion progresses closer to a target condition
  * while for loops run a set number of times
  * while loops run until a condition is no longer met.
* Recursion is declarative because you set the state you want to reach and for/while loops are iterative because you have to set the number of repetitions

## Recursion Implementation

* Find sum from 1 to n
* Find Factorial using Recursion
* Fibonacci series using Recursion
* Binary search implementation
* Reverse a LinkedList using recursion
* Detect a Palindrome
  * A **palindrome** is a word that reads the same backward as it does forward. Examples include Racecar, Level, Kayak, Reviver, Civic, etc.
* Balanced parentheses question using recursion
* Convert tree to a doubly LinkedList using recursion
* Reverse a stack using recursion
* Tree traversal (For simplicity list within a list traversal)
* Quicksort implementation
* Merge sort implementation

## References for Further Reading

{% embed url="<https://www.educative.io/blog/recursion-in-python-tutorial>" %}

{% embed url="<https://www.educative.io/blog/recursion>" %}

{% embed url="<https://realpython.com/python-recursion/>" %}

{% embed url="<https://medium.com/@codingfreak/recursion-practice-problems-d8c6b4fbb04e>" %}