MSK Institute • Shikohabad
Loading Page Content...
Preparing courses, live labs, and learning resources.सामग्री लोड हो रही है, कृपया प्रतीक्षा करें...
Connecting serverPlease wait...
💻 Practical Labs🚀 Free Demo📜 Verified Certificates
Preparing courses, live labs, and learning resources.सामग्री लोड हो रही है, कृपया प्रतीक्षा करें...
In computer science, recursion is a problem-solving technique where a function solves a complex task by calling itself with smaller, simpler inputs. Instead of attempting to solve the entire problem in one monolithic loop, recursion breaks the task down until it reaches a trivial subproblem that can be answered immediately.
Recursion mirrors mathematical induction: if you know how to solve the simplest baseline case, and you know how to reduce an $N$-sized problem to an $(N-1)$-sized problem, you can solve for any $N$.
+-------------------------------------------------------------------------------+
| RECURSION REAL-WORLD ANALOGIES |
+-------------------------------------------------------------------------------+
1. CHANNAPATNA / RUSSIAN NESTING DOLLS (Matryoshka):
- You hold a large painted wooden doll in your hands.
- You open Doll #4 -> Inside is Doll #3.
- You open Doll #3 -> Inside is Doll #2.
- You open Doll #2 -> Inside is Doll #1.
- You open Doll #1 -> Inside is a tiny, solid wooden figure that
CANNOT be opened.
* This is the **BASE CASE** (the stopping condition).
- Now, you snap the shells back together in reverse sequence:
Doll 1 into Doll 2, into Doll 3, into Doll 4.
* This is the **UNWINDING PHASE** of the call stack!
2. THE SALON / BARBER SHOP OPPOSING MIRRORS:
- When you sit between two parallel mirrors, the reflection reflects
the reflection infinitely.
- Without a physical barrier or end (a base case), the loop continues
indefinitely into infinity.
+-------------------------------------------------------------------------------+Let us trace the execution of factorial(4) through the Python Call Stack:
Every valid recursive function must possess two non-negotiable components:
Output:
RecursionErrorIf a recursive function lacks a base case, or if its recursive step fails to move toward the base case, the function calls itself indefinitely.
Python protects system memory from crashing by enforcing a maximum recursion depth limit (typically 1,000 stack frames):
You can inspect the recursion limit using the standard sys module:
Calculate the sum of all digits of a number: $482 \rightarrow 4 + 8 + 2 = 14$.
(n % 10) + sum_of_digits(n // 10).Output:
Reverse a string recursively:
reverse_string(all_characters_except_last).Output:
| Feature | Recursion | Iteration (for / while Loops) |
|---|---|---|
| Termination | Base case reached. | Loop condition evaluates to False. |
| Memory Overhead | $O(N)$ auxiliary stack memory (stack frames). | $O(1)$ constant auxiliary memory. |
| Execution Speed | Slightly slower due to function call push/pop overhead. | Noticeably faster in Python. |
| Best Suited For | Tree traversals, nested dictionaries, JSON structures, divide-and-conquer. | Linear sequences, numeric counting, simple filters. |
| Best Practice (DO) | Dangerous Anti-Pattern (DON'T) |
|---|---|
| DO verify that your base case executes and handles boundary inputs (like $0$ or negative numbers). | DON'T write recursive functions without an explicit stopping base case. |
| DO ensure the arguments passed to recursive calls strictly advance toward the base case. | DON'T use recursion for simple loops (like counting to 100); loops are faster and use $O(1)$ memory. |
| DO be mindful of Python's default 1,000 recursion frame limit. | DON'T implement naive recursive Fibonacci without memoization, as it causes $O(2^N)$ exponential slowdowns. |
RecursionError: maximum recursion depth exceeded.return StatementIf a function computes a value but doesn't return it, Python returns None by default:
global KeywordReading a global variable is permitted, but assigning to it creates a local variable unless explicitly declared:
A. A while loop and a for loop B. A base case and a recursive step C. A lambda expression and a docstring D. Positional arguments and keyword arguments
A. MemoryOverflowException B. RecursionError: maximum recursion depth exceeded C. SystemStackFault D. ZeroDivisionError
mystery(3) given the following function definition?A. 6 B. 3 C. 5 D. 1
A. Python allocates new stack memory for child threads B. Base case values are returned and stack frames are popped in reverse order as calculations resolve C. Python resets all local variables to zero D. The compiler optimizes bytecode into C machine code
A. Loops can handle floating-point numbers, while recursion cannot B. Python does not support Tail Call Optimization (TCO), meaning every recursive call allocates a new stack frame in $O(N)$ memory C. Recursion is prohibited by PEP 8 D. Python limits functions to 5 total invocations
Build an automated storage audit engine for a corporate cloud drive (Google Drive / Nextcloud).
Filesystems are inherently hierarchical: folders contain files as well as nested sub-folders, which in turn contain more files and folders.
Write a recursive function: calculate_directory_size_bytes(directory_node)
Each folder node is represented as a dictionary:
subdirectories is empty, simply return the sum of the sizes of all files in the current folder.calculate_directory_size_bytes() for every nested folder in subdirectories.How data and code flow step-by-step
In the next lesson, we will continue your Python learning journey with Scope of Variables in Functions (14: Functions).
👉 Continue to Next Lesson: Scope of Variables in Functions →
Continue learning with hands-on practice, examples, and exercises in the upcoming topic.
| Previous Lesson | Next Lesson |
|---|---|
| Lambda Functions | Scope of Variables in Functions |
Test your understanding of this lesson with 5 questions. Each question has one correct answer.