The functions which calls itself with a exit condition
There are two common types of recursion :
Head Recursion: Where you call the recursion function first and perform operations which you need to do e.g. print(number) in the below case.
def head_recursion(number):
if number <= 0:
return
head_recursion(number - 1)
print(number, end=" ")
head_recursion(4)
# Output: 1 2 3 4
Head recursion is useful for post-order tree traversal, backtracking, and processing values in reverse order.
Tail Recursion: Where you perform the action print(number)before calling the function itself.
Simply put ~ the recursive call is the final operation performed by the function.
def tail_recursion(number):
if number <= 0:
return
print(number, end=" ")
tail_recursion(number - 1)
tail_recursion(4)
# Output: 4 3 2 1
Tail recursion is useful when each call passes an updated value or state to the next call, such as factorial calculation, list traversal, or repeated processing. In some languages, tail recursion can use constant stack space when the compiler or runtime supports tail-call optimization.
It is just the ordering of the function calls which differs head and tail recursion.
Base Condition Intro
def printMe():
print("Hello abhi")
printMe()
The above function will keep calling itself until the system reaches its recursion or stack limit because it doesn't know where to exit.
To make an actual recursive function that works in a real-world system, we need to add a base condition so it knows where to stop.
However, adding a base condition alone does not guarantee that recursion will stop. Each recursive call must also move towards that condition.
As recursion runs, each active call adds a new layer to the call stack. If recursion creates more calls than the stack can handle, the program may end with a recursion-limit error or stack-overflow error.
Stack Overflow
A stack overflow happens when active function calls use more call-stack space than the system allows. It can happen due to the following reasons:
The recursive function doesn't have a base condition.
The base condition exists, but the recursive calls never reach it.
The input requires more recursive calls than the stack can handle.
Recursion Tree
A recursion tree is a diagram which shows how recursive function calls are created. Each node represents one function call, and the branches below it represent the next recursive calls made by that function.
Let's take the Fibonacci function as an example:
def fibonacci(number):
if number <= 1:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(4))
# Output: 3
The recursion tree for fibonacci(4) looks like this:
f(4)=3
/ \
/ \
f(3)=2 f(2)=1*
/ \ / \
f(2)=1* f(1)=1* f(1)=1* f(0)=0*
/ \
f(1)=1* f(0)=0*
* = repeated calculation
Base cases: f(0) and f(1)
The calls continue until they reach the base condition. After that, the results return back through the tree and are added together.
A recursion tree helps us understand:
The order in which recursive calls are created.
The maximum depth of the recursion.
How much repeated work is being done.
In the above tree, calls marked with an asterisk (*) are calculated more than once. For larger inputs, this repeated work can make the function slow. We can avoid it by storing calculated results and reusing them. This technique is called memoization.
When to Use Recursion
Recursion is useful when a problem can be divided into smaller versions of the same problem. Common examples include tree traversal, directory traversal, divide-and-conquer problems, and backtracking.
Before using recursion, check the following:
There is a clear base condition.
Each recursive call moves towards the base condition.
The recursion will not become too deep for the available call stack.
The function is not repeating too much work.
For simple repetition, a loop may be easier to understand and may use less stack space.
