- Aliases
- and operator
- Arrays
- Booleans
- Classes
- Code blocks
- Comments
- Conditional statements
- Console
- Data structures
- datetime module
- Decorator
- Dictionaries
- Docstrings
- enum
- enumerate() function
- Equality operator
- Exception handling
- False
- File handling
- Filter()
- Floats
- For loops
- Formatted strings
- Functions
- Generator
- Globals()
- Greater than operator
- Greater than or equal to operator
- If statement
- in operator
- Indices
- Inequality operator
- Integers
- Iterator
- Lambda function
- Less than operator
- Less than or equal to operator
- List append() method
- List comprehension
- List count()
- List insert() method
- List pop() method
- List sort() method
- Lists
- Logging
- map() function
- Match statement
- Math module
- Merge sort
- Min()
- Modules
- Multiprocessing
- Multithreading
- None
- not operator
- OOP
- or operator
- Parameters
- print() function
- Property()
- Random module
- range() function
- Recursion
- Reduce()
- Regular expressions
- requests Library
- return statement
- round() function
- Sets
- SQLite
- String decode()
- String find()
- String join() method
- String replace() method
- String split() method
- String strip()
- Strings
- Ternary operator
- time.sleep() function
- True
- try...except statement
- Tuples
- Variables
- While loops
- Zip function
PYTHON
Python Recursion: Syntax, Usage, and Examples
Python recursion is a technique where a function calls itself to solve a problem in a step-by-step manner. It is commonly used for solving problems that can be broken down into smaller subproblems, such as calculating factorials, Fibonacci sequences, and performing binary search. It's one of the foundational concepts in python programming, especially useful for beginners exploring problem-solving techniques.
How to Use Recursion in Python
A recursive function in Python follows a simple structure:
def recursive_function(parameters):
if base_condition:
return result
else:
return recursive_function(modified_parameters)
- Base condition: The stopping point that prevents infinite recursion.
- Recursive call: The function calls itself with modified parameters.
Example: Simple Recursion
def countdown(n):
if n <= 0: # Base case
print("Done!")
else:
print(n)
countdown(n - 1) # Recursive call
countdown(5)
Output:
5
4
3
2
1
Done!
This example demonstrates recursion with a base case to stop the function. You could also add an append to a list inside the recursive call if you needed to store results in order.
When to Use Recursion in Python
Recursion is useful when:
- Solving problems that can be divided into smaller subproblems
- Examples: Factorial calculations, Fibonacci sequences, and tree traversals.
- These are classic examples of a recursive solution, often introduced early to beginners.
- Working with nested data structures
- Example: Traversing a directory structure or processing a JSON object.
- Implementing algorithms like binary search and depth-first search
- Recursion naturally follows the structure of these problems and aligns with a call stack execution model.
Examples of Recursion in Python
Factorial Recursion
Factorial of n
(n!
) is n * (n-1) * (n-2) ... * 1
.
def factorial(n):
if n == 0:
return 1 # Base case
return n * factorial(n - 1) # Recursive call
print(factorial(5)) # Output: 120
Fibonacci Recursion
The Fibonacci sequence follows the rule: F(n) = F(n-1) + F(n-2)
, where F(0) = 0
and F(1) = 1
.
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6)) # Output: 8
Fibonacci is often optimized using memoization to avoid redundant calculations - a common task in data science workflows where performance matters. You can modify this limit using sys.setrecursionlimit()
, but increasing the recursion limit too much may cause crashes due to a full call stack.
Binary Search with Recursion
Binary search efficiently finds an element in a sorted list by dividing the search range in half.
def binary_search(arr, target, left, right):
if left > right:
return -1 # Base case: target not found
mid = (left + right) // 2
if arr[mid] == target:
return mid # Base case: target found
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, right) # Search right half
else:
return binary_search(arr, target, left, mid - 1) # Search left half
numbers = [1, 3, 5, 7, 9, 11]
print(binary_search(numbers, 7, 0, len(numbers) - 1)) # Output: 3
Learn More About Recursion in Python
Recursion Depth Limit in Python
Python limits recursion depth to prevent infinite recursion, causing a RecursionError
.
import sys
print(sys.getrecursionlimit()) # Output: Typically 1000
You can modify this limit using sys.setrecursionlimit()
, but increasing it too much may cause crashes.
Maximum Recursion Depth Exceeded Error
If a function calls itself too many times without reaching a base case, Python raises:
RecursionError: maximum recursion depth exceeded while calling a Python object
This often occurs when debug steps are missed, or the base case is incorrectly defined.
Tail Recursion in Python
Tail recursion is an optimization where the recursive call is the last operation in a function. Python does not optimize tail recursion, so deep recursion can still cause stack overflow.
def tail_recursive_factorial(n, accumulator=1):
if n == 0:
return accumulator
return tail_recursive_factorial(n - 1, n * accumulator)
print(tail_recursive_factorial(5)) # Output: 120
Using Memoization to Optimize Recursion
Memoization stores previously computed results to avoid redundant calculations, making recursive functions more efficient.
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_memo(n):
if n <= 0:
return 0
elif n == 1:
return 1
return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
print(fibonacci_memo(50)) # Output: 12586269025
Memoization is a vital technique in data science when working with computationally heavy recursive problems.
When to Use Iteration Instead of Recursion
Recursion is elegant but can be inefficient for large inputs. In such cases, loops are preferable.
Factorial with iteration:
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial_iterative(5)) # Output: 120
Sign up or download Mimo from the App Store or Google Play to enhance your programming skills and prepare for a career in tech.