Question bank — Recursion — call stack visualization, base case, recursive case

False. It needs at least one, but may have several — e.g. Fibonacci returns directly for both n == 0 and n == 1. The rule is "every path down must hit some base case", not "there is exactly one".

False. Smaller-input alone is not enough — a value must actually be caught and returned by a base case. Without if n == 0: return ..., the shrinking sails right past $0$ into fact(-1), fact(-2), … forever.

True. Recursion and iteration are equally powerful; any recursion can be simulated with an explicit stack and a while loop (see Iteration — for and while loops). Recursion is often just closer to the maths, not more capable.

False. Each call gets its own independent frame, so n = 3, n = 2, n = 1, n = 0 all coexist at the deepest moment. Same name, different boxes.

False. The stack is LIFO: the last frame pushed (fact(0), the base case) finishes first, then the others unwind outward. fact(3) returns last of all.

Usually true on memory (each frame costs stack space, capped near depth 1000), but "always" is too strong — with memoization a recursive solution can match or beat a naive loop. Clarity, not speed, is recursion's main win.

False. That is mutual (indirect) recursion — is_even(n) calling is_odd(n-1) calling is_even(n-2). Recursion means "eventually calls itself", directly or through a chain.

False for computing a value. Without return, the sub-call's result is discarded and the function yields None. Printing shows a number on screen but hands nothing back to the caller to combine.

No base case, so it never stops. Python pushes frames until it hits the depth limit → RecursionError: maximum recursion depth exceeded. Add if n == 0: return 1.

The recursive call uses f(n), not f(n-1), so the input never shrinks. It re-asks the identical problem forever and never reaches the base case despite having one.

It returns None. The final line computes a sum but has no return, so the value is thrown away. Fix: return L[0] + summ(L[1:]).

It works but by luck of placement. print is before the check, so it prints 2, 1, 0 then stops. Cleaner is to test the base case first; here a negative call is avoided only because n==0 returns before cd(-1).

Both branches recurse on n-1; the second should be fib(n-2). As written it computes the wrong sequence (and still terminates, so no crash to warn you — a silent logic bug). See Fibonacci and overlapping subproblems.

The input decreases by 1 each time (2.5 → 1.5 → 0.5 → −0.5 → …) but never equals exactly 0, so the base case is skipped forever → RecursionError. Base cases must be reachable from the starting input.

1 2 3, not 3 2 1. The print sits after the recursive call, so it runs during unwinding (coming back up), reversing the visible order.

So the stopping condition is checked first, on every entry. If the recursive call ran before the check, you'd descend one level too deep (or infinitely) before ever asking "should I stop?".

Because the call stack is LIFO — the last frame pushed is the first popped. Each caller is paused waiting on its callee, so nobody above can resume until the one below returns.

Each function call creates a fresh frame with its own local namespace. The name n is a label inside that frame's box, so fact(3)'s n and fact(2)'s n are entirely separate storage.

A print before the call fires during winding (top-down); after the call it fires during unwinding (bottom-up). The two phases visit values in opposite orders.

Because it re-solves the same subproblems many times — fib(3) is recomputed all over the tree. The work explodes exponentially; Memoization and Dynamic Programming fixes it by caching each answer once.

Those structures are self-similar: a folder contains folders, each handled the same way. Recursion mirrors that shape directly — see Tree and Graph Traversal.

Every pending frame occupies real stack memory; unbounded depth would exhaust it and crash the interpreter unpredictably. The cap turns a silent memory blow-up into a catchable RecursionError. See Big-O and Recursion Depth.

It returns 1 immediately with no recursive call. That direct answer is the base case — the ground the whole staircase of calls stands on; remove it and everything collapses.

The base case if not L: return 0 fires at once. An empty problem has a known trivial answer, so no recursion is needed — this is exactly why base cases exist.

The function recurses before ever testing whether to stop, so it descends indefinitely and overflows the stack. The stop condition must be reachable before the next call.

Yes — [7] is not empty, so it computes 7 + summ([]). The empty-list base case is reached on the next call, not this one. One-element inputs are still a recursive case, not a base case.

No — by definition the base case returns without recursing. If it recursed it wouldn't stop anything, and there'd be no guaranteed floor to the descent.