RECURSIVE FUNCTIONS
Example of a recursive function
Note : Any recursive algorithm can be
implemented in iterative approach too
BINARY SEARCH ( let’s search for 27)
0 1 2 3 4 5 6 7 8 9 10
4 9 13 16 19 23 27 32 38 41 50
0 1 2 3 4 5 6 7 8 9 10
4 9 13 16 19 23 27 32 38 41 50
0 1 2 3 4 5 6 7 8 9 10
4 9 13 16 19 23 27 32 38 41 50
More examples on recursion
Common Recursive Problems
1. Factorial Calculation
Calculate the product of all positive integers up to n (n!).
2. Fibonacci Sequence
Find the nth number in the sequence where each number is the sum of the
two preceding ones.
3. Palindrome Check
Determine if a string reads the same forward and backward by comparing
characters recursively.
4. Sum of Natural Numbers
Compute the sum of all numbers from 1 to n by breaking down the problem
into smaller sums.
String Reversal
Reverse a string by recursively processing characters from front to back.
Comparison: Recursive vs Iterative
Feature Recursive Iterative
Elegance Looks cleaner, math-like More mechanical
Easier for real-world
Ease of Understanding Great for teaching recursion
performance
Stack Usage Uses call stack → O(n) space Constant space → O(1)
Slower (due to function call Faster (tight loop, no stack
Speed for Large n
overhead) buildup)
Risk Stack overflow for large n Safe for large n
Debugging Harder to trace (deep calls) Easier (single loop)
Best when problem is recursive Best for linear computation
Use Case
by nature (e.g. tree traversal) like factorial