CS 238 Week 9 Lecture

Overview

James Andro-Vasko introduces recursion in Python as a function calling itself with a changing parameter until it reaches a base case, then returning results through the call stack. Using factorials and lists, he compares recursive solutions with loops and demonstrates Python’s default recursion limit of 1,000, including how `sys.setrecursionlimit` can raise it.

Key takeaways

Every recursive function needs a base case and a recursive step that changes its input toward that case; without either, calls can continue until Python reports a recursion-depth error.
In recursive factorial, calls descend from factorial(5) to factorial(0), then unwind to calculate 5 × 4 × 3 × 2 × 1 = 120.
Python’s default recursion limit is 1,000, and `sys.getrecursionlimit()` and `sys.setrecursionlimit()` inspect and adjust that limit.
Recursive list summation combines the current element with the sum of the remaining elements, using 0 as the sum of an empty remainder.
Recursive list construction can generate a range by prepending each current value to the recursively constructed remainder, stopping when the counter equals the endpoint.

Chapters

0:00 Recursion Basics and Iterative Factorial

Recursion uses a function that calls itself to perform repetition, and is useful for tree and graph traversal, maze paths, and backtracking.
The iterative factorial function multiplies values from 1 through n; for 5!, the loop returns 120.
The factorial definition uses 0! = 1 as its stopping point.

3:23 Recursive Factorial and the Call Stack

The recursive rule computes n! as n multiplied by (n - 1)!, reducing the input toward the base case.
For factorial(5), calls descend through 5, 4, 3, 2, 1, and 0, then return upward to produce 120.
Each function call waits for its recursive result before multiplying by its own n.

10:23 Recursion Errors and Python’s 1,000-Call Limit

A recursive call that repeats the same input, such as factorial(n) calling factorial(n), never approaches a base case and triggers a recursion-depth error.
Omitting the base case also causes calls to continue until Python raises a maximum recursion depth error.
Python’s default recursion limit is 1,000; `sys.getrecursionlimit()` checks it, and `sys.setrecursionlimit(1100)` allows the factorial of 1,050 to run in the demonstrated example.

14:15 Recursive List Sum and List Construction

A recursive `list_sum` function uses an index as a counter, adds the current element to the sum from index + 1, and returns 0 when the index is out of bounds.
Applying `list_sum` to [3, 2, 1, 6, 5] returns 17.
A recursive list constructor returns an empty list when its counter reaches n; otherwise, it prepends the current value to the list built from the next value.
Calling the constructor with 0 and 10 builds [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], while starting at 5 builds [5, 6, 7, 8, 9].

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, James Andro-Vasko.