Python - Recursive Functions

In the previous sections, we learned how one function can call another function.

Python also allows a function to call itself.

A function that calls itself is called a Recursive Function.

The process of a function calling itself repeatedly until a specific condition is satisfied is known as Recursion.

Recursion is a powerful programming technique used to solve problems that can be divided into smaller versions of the same problem.

A Recursive Function is a function that calls itself either directly or indirectly until a terminating condition is reached.

The terminating condition is called the Base Case.

Many real-world problems are naturally recursive.

Instead of writing complicated loops, recursion provides a cleaner and easier solution.

It is especially useful when solving problems that involve repeated subdivision into smaller sub-problems.

Common examples include:

• Factorial Calculation
• Fibonacci Series
• Tree Traversal
• Directory/File Traversal
• Binary Search
• Tower of Hanoi

Every recursive function contains two important parts:

1. Base Case
2. Recursive Case

The Recursive Case keeps calling the function repeatedly.

The Base Case stops further recursive calls and prevents infinite recursion.

Component	Purpose
Base Case	Stops the recursion.
Recursive Case	Calls the function again.

The function display() calls itself continuously.

Since there is no Base Case, the recursive calls never stop.

Python keeps creating new function calls until the maximum recursion depth is exceeded.

Finally, Python raises a RecursionError.

Infinite recursion occurs when a recursive function has no terminating condition.

Every function call creates another function call.

Eventually, Python runs out of available call stack space.

To prevent this situation, every recursive function must include a Base Case.

The function starts with the value 5.

Each recursive call decreases the value of n by 1.

When n becomes 0, the Base Case executes and recursion stops.

Function Call	Output
display(5)	5
display(4)	4
display(3)	3
display(2)	2
display(1)	1
display(0)	Stops

Step	Action
1	Function is called.
2	Base Case is checked.
3	If Base Case is false, the function calls itself.
4	Each recursive call receives a smaller problem.
5	When the Base Case becomes true, recursion stops.

Normal Function	Recursive Function
Does not call itself.	Calls itself.
Usually uses loops for repetition.	Uses repeated function calls.
Generally easier for simple repetitive tasks.	Better for problems that can be divided into smaller sub-problems.

• Factorial calculation.
• Fibonacci sequence.
• Binary Search.
• Tree Traversal.
• Graph Traversal.
• Directory and File System Traversal.
• Tower of Hanoi.

The Factorial of a positive integer is the product of all positive integers from 1 to that number.

Factorial is represented by the symbol !.

It is one of the most common examples used to understand Recursion because the problem can be divided into smaller versions of itself.

The mathematical formula for factorial is:

No output captured.

The recursive definition of factorial is:

No output captured.

The recursion must stop when the value becomes 0 or 1.

Both 0! and 1! are equal to 1.

The function receives a number from the user.

If the number becomes 0, the Base Case executes and returns 1.

Otherwise, the function calls itself with n-1.

Each recursive call multiplies the current number with the factorial of the next smaller number.

Finally, all recursive calls return one by one and the final factorial value is produced.

Function Call	Status
factorial(5)	Calls factorial(4)
factorial(4)	Calls factorial(3)
factorial(3)	Calls factorial(2)
factorial(2)	Calls factorial(1)
factorial(1)	Calls factorial(0)
factorial(0)	Returns 1 (Base Case)

Recursive Call	Returned Value
factorial(0)	1
factorial(1)	1
factorial(2)	2
factorial(3)	6
factorial(4)	24
factorial(5)	120

Step	Operation
1	factorial(5) is called.
2	It calls factorial(4).
3	Each function keeps calling the next smaller value.
4	When factorial(0) is reached, 1 is returned.
5	Each pending function multiplies its value while returning.
6	The final answer becomes 120.

Recursive functions provide an elegant and efficient solution for many problems that can be divided into smaller sub-problems.

Instead of writing long and complex iterative code, recursion often produces shorter and easier-to-understand programs.

Some important advantages of recursion are listed below.

• Produces shorter and cleaner code.
• Makes programs easier to understand for recursive problems.
• Suitable for mathematical problems such as Factorial and Fibonacci.
• Very useful for Tree Traversal and Graph Traversal.
• Reduces the complexity of solving divide-and-conquer problems.
• Used extensively in searching and sorting algorithms.
• Improves readability for naturally recursive problems.

Although recursion is powerful, it also has some limitations.

Each recursive function call creates a new stack frame in memory.

If recursion continues for many levels, more memory is consumed and the program becomes slower.

• Consumes more memory because of the Call Stack.
• Slower than loops for many simple problems.
• Improper Base Case causes infinite recursion.
• May generate RecursionError.
• Debugging recursive functions is more difficult than loops.
• Not suitable for every programming problem.

Recursion should be used only when it makes the solution simpler and more natural.

Some common situations where recursion is preferred are:

• Factorial Calculation
• Fibonacci Series
• Tree Traversal
• Directory Traversal
• Binary Search
• Depth First Search (DFS)
• Tower of Hanoi
• Merge Sort and Quick Sort

Recursion should generally be avoided when:

• A simple loop can solve the problem easily.
• The recursion depth may become very large.
• Memory usage is an important concern.
• Performance is more important than code simplicity.

Recursion	Loop
Function calls itself.	Repeats statements using loops.
Uses Call Stack.	Does not create recursive stack frames.
Consumes more memory.	Consumes less memory.
Usually slower.	Usually faster.
Code is shorter for recursive problems.	Code may become longer for recursive problems.
Needs a Base Case.	Needs a Loop Condition.
Best for divide-and-conquer problems.	Best for repetitive tasks.

Normal Function	Recursive Function
Does not call itself.	Calls itself.
Usually uses loops.	Uses recursive calls.
Consumes less memory.	Consumes more memory.
Easy to debug.	Comparatively difficult to debug.
Suitable for simple iterative tasks.	Suitable for recursive problems.

Recursion is widely used in modern software development.

• Binary Search Algorithms
• Tree Traversal (Preorder, Inorder, Postorder)
• Graph Traversal (DFS)
• Merge Sort
• Quick Sort
• File and Directory Traversal
• Artificial Intelligence Search Algorithms
• Dynamic Programming Problems
• Expression Evaluation
• Compiler Design

1. What is a Recursive Function?
2. What is the Base Case?
3. Why is the Base Case necessary?
4. What is Infinite Recursion?
5. What is Call Stack?
6. Explain the execution of the Factorial Program.
7. Differentiate between Recursion and Loop.
8. What are the advantages and disadvantages of recursion?
9. When should recursion be preferred over loops?
10. Explain RecursionError with an example.