Summary  
This chapter covers recursion, detailing how to define a base case and a recursive case so a function calls itself with simpler inputs, and explains how the call stack manages these nested calls.  

General domain of usage  
Processing tree data structures

A **recursive function** is a function that calls itself to solve a problem by breaking it down into smaller, simpler parts.



Definition

The key elements of recursion are:
- **Base case**: the condition that stops the recursion;
- **Recursive case**: the part where the function calls itself with a simpler input.

## Why Use Recursion?

Some problems can be naturally expressed in terms of smaller subproblems. Recursion provides a clean and elegant way to solve these by having a function call itself to handle the simpler cases. It is commonly used in tasks like processing trees, exploring paths, or breaking down structures (e.g., lists, strings).



def print_message(message, times):
    if times > 0:                              # Base case: stop when times is 0
        print(message)
        print_message(message, times - 1)     # Recursive case

print_message("Hello, Recursion!", 3)

Go step by step to understand how this works:

1. `times = 3` → condition is true, print message, call `print_message(message, 2)`;
2. `times = 2` → condition is true, print message, call `print_message(message, 1)`;
3. `times = 1` → condition is true, print message, call `print_message(message, 0)`;
4. `times = 0` → condition is false, recursion stops.

**Result**: the message is printed three times.



## The Call Stack

Each time the function calls itself, it adds a new frame to the **call stack** — a memory structure that keeps track of active function calls. Once the base case is reached, each previous call completes one by one in reverse order.

Every recursive function must have a base case. Without it, the function will call itself forever and cause a `RecursionError`.

Note

import unittest

def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)

class TestListSum(unittest.TestCase):

    def test_list_sum_basic(self):
        import user_code
        try:
            result = user_code.list_sum([1, 2, 3, 4, 5])
            expected = 15
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[1, 2, 3, 4, 5]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `15` for `[1, 2, 3, 4, 5]`.", failure_message)

    def test_list_sum_another_list(self):
        import user_code
        try:
            result = user_code.list_sum([10, 20, 30])
            expected = 60
            condition = result == expected
            failure_message = f"Expected `{expected}` for `[10, 20, 30]`, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, f"The `list_sum` returns `60` for `[10, 20, 30]`.", failure_message)

    def test_list_sum_empty(self):
        import user_code
        try:
            result = user_code.list_sum([])
            expected = 0
            condition = result == expected
            failure_message = f"Expected `{expected}` for an empty list, but got `{result}`."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` correctly returns `0` for an empty list.", failure_message)

    def test_recursion_used(self):
        import user_code
        import inspect
        try:
            source = inspect.getsource(user_code.list_sum)
            condition = "list_sum(" in source.split("def list_sum")[1]
            failure_message = "Expected `list_sum` to call itself recursively."
        except AttributeError:
            condition = False
            failure_message = "The function `list_sum` is not defined."
        _dynamic_test(self, condition, "The `list_sum` function uses recursion.", failure_message)

if __name__ == '__main__':
    unittest.main()

test_main.py

Gain a solid understanding of how functions shape Python programming. Master defining and calling functions, working with arguments, handling return values, and creating flexible, efficient code using recursion and lambda expressions.

Explore what functions are and why they're essential in Python. Learn how to create functions, define arguments, handle return values, and use built-in functions effectively.

Learn how positional and optional arguments work in Python. Build adaptable functions that handle different inputs and improve flexibility in your code.

Understand how to work with arbitrary and keyword arguments to handle variable input sizes. Learn how these techniques make your functions more dynamic and organized.

Discover how return values represent a function's output. Learn to return single or multiple values, use None, and explore generators for more advanced data flow control.

Unlock advanced function concepts with recursion and lambda functions. Learn how recursion solves repetitive problems and how lambda expressions create concise, one-line functions.

Recursion

Why Use Recursion?

A Simple Example

The Call Stack

Solution