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
Last updated
Was this helpful?