DSA Recursion

How it works

The fixture sums a small nonnegative integer countdown. The argument decreases at every call and zero returns directly. Python does not generally eliminate tail-recursive calls, so a mathematically valid recurrence can still exceed the interpreter’s recursion limit on a large input. Do not raise that limit casually to hide an algorithm design issue; use an iterative method when it expresses the work more safely.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as recursion.py and run python recursion.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def countdown_total(n):
    if type(n) is not int or n < 0:
        raise ValueError("Expected a nonnegative integer")
    if n == 0:
        return 0
    return n + countdown_total(n - 1)

print(countdown_total(4))
print(countdown_total(0))

Expected result

10
0

The calls reduce four to zero and combine the returned values into ten. The small fixture is deliberately within the normal recursion limit. Later divide-and-conquer and tree examples must also account for recursion depth, not just the number of comparisons.

Time, space and assumptions

There are n+1 calls, giving O(n) time and O(n) stack frames in this implementation under a unit-cost arithmetic model.