fib Function Overview This function calculates numbers in the Fibonacci sequence using recursion plus memoization. The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, ... Each number is the sum of the previous two. For example: Python Execută fib(6) returns: Python Execută 8 because: fib(6) = fib(5) + fib(4) = 5 + 3 = 8 Code Python Execută def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n] Components Function Definition — declares the Fibonacci function and its parameters. Memo Check — looks for already-computed answers. Base Case — stops recursion at the smallest Fibonacci values. Recursive Calculation — computes Fibonacci values from smaller ones. Memo Storage — saves results for reuse. Final Return — returns the computed Fibonacci number. Step-by-Step Breakdown 1. Function Definition Python Execută def fib(n, memo={}): What it does Defines a function named fib that takes a number n and an optional dictionary called memo. How it works n is the Fibonacci position to calculate. memo is a dictionary used to store results already calculated. Example: Python Execută fib(5) starts with: Python Execută n = 5 memo = {} The dictionary grows as recursive calls happen. Why it's there Without memo, the function would repeatedly recalculate the same Fibonacci numbers, making it extremely slow. Connections This definition sets up everything the later parts rely on: recursion, caching, and returning values efficiently. 2. Memo Check Python Execută if n in memo: return memo[n] What it does Checks whether the Fibonacci value for n has already been computed. How it works The dictionary stores results like: Python Execută { 2: 1, 3: 2, 4: 3 } If fib(4) is called again later, the function immediately returns: Python Execută memo[4] instead of recalculating it. Why it's there This is the core optimization called memoization. Memoization means: "Save expensive results so future calls can reuse them." Without this step, recursive Fibonacci becomes exponentially slow. Connections This works together with the recursive calculation section, because recursive calls generate many repeated subproblems. 3. Base Case Python Execută if n <= 1: return n What it does Stops recursion when the smallest Fibonacci values are reached. How it works The Fibonacci sequence begins with: fib(0) = 0 fib(1) = 1 So: Python Execută fib(0) -> 0 fib(1) -> 1 These are returned directly. Why it's there Recursive functions need a stopping condition. Without a base case, recursion would continue forever until Python raises: RecursionError Connections The recursive calculation repeatedly reduces n until these base cases are reached. 4. Recursive Calculation Python Execută memo[n] = fib(n - 1, memo) + fib(n - 2, memo) What it does Calculates the Fibonacci value using the mathematical Fibonacci rule. How it works The Fibonacci rule is: F(n)=F(n−1)+F(n−2) Example for fib(5): fib(5) = fib(4) + fib(3) = 3 + 2 = 5 The function keeps calling itself with smaller values until it reaches the base case. Why it's there This mirrors the actual mathematical definition of Fibonacci numbers, making the code concise and readable. Connections Depends on the base case to stop recursion. Benefits heavily from memoization because many recursive calls repeat. 5. Memo Storage Python Execută memo[n] = ... What it does Stores the computed Fibonacci value in the dictionary. How it works After computing: Python Execută fib(5) = 5 the dictionary becomes: Python Execută { 5: 5 } Future calls to fib(5) return instantly from the memo check. Why it's there Caching turns the algorithm from inefficient recursion into an efficient dynamic programming approach. Connections This directly supports the memo check at the top of the function. 6. Final Return Python Execută return memo[n] What it does Returns the computed Fibonacci value. How it works By this point: either the value was already cached, or it was just computed and stored. The function returns the dictionary entry. Why it's there Using memo[n] guarantees a single consistent source for the value. Connections This completes the recursive workflow: check cache, compute if necessary, store result, return result. Full Execution Walkthrough Calling: Python Execută fib(5) creates this chain: fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ │ ├── fib(1) → 1 │ │ │ └── fib(0) → 0 │ │ └── fib(1) → 1 │ └── fib(2) → reused from memo └── fib(3) → reused from memo Notice: fib(2) and fib(3) are reused instead of recalculated. That reuse is the whole reason memoization matters. Time Complexity Without memoization: O(2 n ) The function repeats huge amounts of work. With memoization: O(n) Each Fibonacci number is computed only once. Important Python-Specific Issue This code contains a famous Python pitfall: Python Execută memo={} as a default argument. Default mutable objects in Python are shared across function calls. Example: Python Execută fib(5) fib(10) The second call reuses the same dictionary from the first call. That may be intentional here, but it often causes confusing bugs. A safer version is: Python Execută def fib(n, memo=None): if memo is None: memo = {} if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n] This creates a fresh dictionary each top-level call. Common Pitfalls | Type | Mistake | Consequence | Fix | | --- | --- | --- | --- | | Python-specific | Using memo={} carelessly | Shared state between calls | Use memo=None and create a new dictionary inside | | Recursion | Forgetting the base case | Infinite recursion and RecursionError | Always define stopping conditions | | Logic | Not passing memo into recursive calls | Memoization stops working | Pass memo into every recursive call | | Performance | Using plain recursion without caching | Extremely slow execution | Add memoization or iterative dynamic programming | | Understanding | Thinking recursion runs linearly | Hard to debug recursive trees | Trace small examples like fib(4) manually | Memory Aids Acronym CBSR Check cache Base case Solve recursively Return stored value That is the exact flow of the function. Analogy Imagine solving math homework with sticky notes. First time solving question 8, you do the full work. You write the answer on a sticky note. Next time someone asks question 8, you read the sticky note instantly. The sticky notes are the memo dictionary. Visual Story A climber is trying to reach step 6 of a staircase. To reach any step, they must stand on the two previous steps first. The climber keeps asking, “How do I get to step 5? Step 4?” Eventually they reach steps 1 and 0, which are simple and known already. Each time they solve a step, they write it in a notebook. Later, whenever they need step 4 again, they read the notebook instead of climbing all over again. The notebook is the memo dictionary, and it prevents wasted work. 5 Questions to Test Yourself 1. Recall What is the purpose of the memo dictionary? 2. Comprehension Why does the function need the condition: Python Execută if n <= 1: 3. Application What happens when you call: Python Execută fib(4) What value is returned? 4. Analysis Why is memoization especially important for recursive Fibonacci implementations? 5. Synthesis Rewrite the function so it avoids the mutable default argument issue while keeping memoization. Answer Key 1. Recall The memo dictionary stores Fibonacci values that were already computed so the function can reuse them instead of recalculating. Correct answer must show Understanding that memoization is caching previously computed results. 2. Comprehension The base case stops recursion when the function reaches known Fibonacci values (0 and 1). Correct answer must show Recognition that recursion must eventually terminate. 3. Application Python Execută fib(4) returns: Python Execută 3 because: fib(4) = fib(3) + fib(2) = 2 + 1 = 3 Correct answer must show Correct recursive expansion and final value. 4. Analysis Recursive Fibonacci creates many repeated calculations. For example, fib(3) may be computed multiple times during one call. Memoization stores results so each Fibonacci number is calculated once, reducing time complexity from exponential to linear. Correct answer must show Awareness of duplicated recursive work and performance improvement. 5. Synthesis Python Execută def fib(n, memo=None): if memo is None: memo = {} if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n] Correct answer must show Replacement of the mutable default dictionary with None. Where to Go Next Foundation Learn recursion thoroughly: call stack, base cases, recursive decomposition. These ideas appear throughout algorithms and tree processing. Practical Try Python’s built-in memoization decorator: Python Execută from functools import lru_cache Example: Python Execută from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) This automates caching. Frontier Explore dynamic programming and top-down vs bottom-up optimization. Modern systems use these ideas in: AI search, compiler optimization, pathfinding, financial modeling, and machine learning workloads.