Recursion in algorithms occurs when a function/algorithm self-references itself, or ‘calls’ itself. It can be considered an alternative approach to iteration.
Recursive algorithms can sometimes be easier to understand, but a main drawback is the large memory size occupied by the recursive function calls.
Every recursive function must include a base/terminating case, which stops it from call on itself forever
Note: Every recursive function can be converted into an iterative function and vice versa
Structure
def factorial(n): #Definition
if n == 0: #Base case, note there are no recursive calls
return 1
return n*factorial(n-1) #Recursive callCall Stack
In programming languages, the call stack stores the various function calls, which then get evaluated. In recursive functions, the call stack behaves a bit differently:
Recursion Tree
- External Merge Sort
- Factorial Algorithm
- Fibonacci Algorithm
- Fibonacci Sequence
- Master Theorem
- Merge Sort
- Page Rank Algorithm
- Recurrence Relation
- Recursion Tree
- Syntactic Unification Algorithm