{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {
                "language": "markdown"
            },
            "source": [
                "# Functional Practice\n",
                "\n",
                "This section focuses on applied functional techniques: recursion, context managers,\n",
                "and functools patterns that you can use in larger programs.\n"
            ],
            "id": "VSC-fea3876d"
        },
        {
            "cell_type": "markdown",
            "id": "2198d211",
            "metadata": {},
            "source": [
                "```{contents} Outline\n",
                ":local:\n",
                ":depth: 2\n",
                "```"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "5f314860-9191-42fe-ada7-b63b49e61179",
            "metadata": {},
            "source": [
                "## Recursion\n",
                "\n",
                "Recursion is a programming technique where a function calls itself to solve a problem. In functional programming, recursion is often the natural way to repeat work because pure functions avoid mutating loop counters or other external state.\n",
                "\n",
                "Every recursive function needs:\n",
                "\n",
                "1. **Base case**: A condition that stops the recursion\n",
                "\n",
                "2. **Recursive case**: The function calling itself with modified parameters\n",
                "\n",
                "Recursion is particularly useful for problems that can be broken down into smaller, similar subproblems.\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "8d4cc079",
            "metadata": {},
            "outputs": [],
            "source": [
                "# Classic example: Factorial\n",
                "def factorial(n):\n",
                "    # Base case\n",
                "    if n == 0 or n == 1:\n",
                "        return 1\n",
                "    # Recursive case\n",
                "    else:\n",
                "        return n * factorial(n - 1)\n",
                "\n",
                "print(factorial(5))  # Output: 120\n",
                "print(factorial(0))  # Output: 1"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "b8d051e2",
            "metadata": {},
            "outputs": [],
            "source": [
                "# Fibonacci sequence\n",
                "# This direct recursive version is intentionally inefficient; later, @lru_cache fixes that.\n",
                "def fibonacci(n):\n",
                "    if n <= 1:\n",
                "        return n\n",
                "    else:\n",
                "        return fibonacci(n - 1) + fibonacci(n - 2)\n",
                "\n",
                "# Generate first 10 Fibonacci numbers\n",
                "for i in range(10):\n",
                "    print(fibonacci(i), end=' ')\n",
                "print()  # Output: 0 1 1 2 3 5 8 13 21 34"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "b3e0a1fa",
            "metadata": {},
            "outputs": [],
            "source": [
                "# Tree traversal example\n",
                "def print_directory(path, level=0):\n",
                "    \"\"\"Recursively print directory structure\"\"\"\n",
                "    import os\n",
                "    if os.path.exists(path):\n",
                "        print('  ' * level + os.path.basename(path))\n",
                "        if os.path.isdir(path):\n",
                "            for item in os.listdir(path)[:3]:  # Limit to first 3 items\n",
                "                item_path = os.path.join(path, item)\n",
                "                print_directory(item_path, level + 1)\n",
                "\n",
                "# Example usage (commented out to avoid file system dependency)\n",
                "# print_directory('/usr/local')"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "43762687",
            "metadata": {},
            "source": [
                "### Recursion vs Iteration\n",
                "\n",
                "**Advantages of recursion:**\n",
                "- Elegant and intuitive for certain problems\n",
                "- Mirrors mathematical definitions\n",
                "- Good for tree/graph traversal\n",
                "\n",
                "**Disadvantages:**\n",
                "- Can be slower due to function call overhead\n",
                "- Risk of stack overflow with deep recursion\n",
                "- May use more memory\n",
                "\n",
                "**Python recursion limit:** Python has a default recursion limit (usually 1000). You can check it with `sys.getrecursionlimit()`."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "a3c7aec0",
            "metadata": {
                "tags": [
                    "thebe-interactive"
                ]
            },
            "outputs": [],
            "source": [
                "### Exercise: Recursive Functions\n",
                "#   1. Write `count_down(n)` that prints n, n-1, ..., 1, then \"Blastoff!\".\n",
                "#      Base case: n <= 0 \u2192 print \"Blastoff!\" and return.\n",
                "#      Recursive case: print n, then call count_down(n - 1).\n",
                "#   2. Write `sum_digits(n)` that returns the sum of the digits of a positive integer.\n",
                "#      Example: sum_digits(1234) \u2192 10; sum_digits(99) \u2192 18.\n",
                "#      Hint: base case is n < 10; use n % 10 and n // 10 for the recursive case.\n",
                "### Your code starts here.\n",
                "\n",
                "\n",
                "\n",
                "\n",
                "### Your code ends here."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "d35e833f",
            "metadata": {
                "tags": [
                    "hide-input"
                ]
            },
            "outputs": [],
            "source": [
                "### Solution\n",
                "def count_down(n):\n",
                "    if n <= 0:\n",
                "        print(\"Blastoff!\")\n",
                "    else:\n",
                "        print(n)\n",
                "        count_down(n - 1)\n",
                "\n",
                "def sum_digits(n):\n",
                "    if n < 10:\n",
                "        return n\n",
                "    return n % 10 + sum_digits(n // 10)\n",
                "\n",
                "count_down(5)\n",
                "print(sum_digits(1234))  # 10\n",
                "print(sum_digits(99))    # 18"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "d89b6fe6",
            "metadata": {},
            "source": [
                "## Context Managers\n",
                "\n",
                "Context managers are objects that define what happens at the start and end of a `with` statement. They ensure proper resource management and cleanup, even if an exception occurs.\n",
                "\n",
                "They connect back to functional programming here because `@contextmanager` is itself a decorator: a higher-order function that transforms a generator function into a context manager."
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "4689ec98",
            "metadata": {},
            "outputs": [],
            "source": [
                "# Creating context managers using contextlib\n",
                "from contextlib import contextmanager\n",
                "\n",
                "@contextmanager\n",
                "def timer():\n",
                "    import time\n",
                "    start_time = time.perf_counter()\n",
                "    print(\"Timer started\")\n",
                "    try:\n",
                "        yield start_time\n",
                "    finally:\n",
                "        end_time = time.perf_counter()\n",
                "        print(f\"Timer finished: {end_time - start_time:.4f} seconds\")\n",
                "\n",
                "# Using the timer context manager\n",
                "with timer() as start:\n",
                "    import time\n",
                "    time.sleep(0.1)  # Simulate some work\n",
                "    print(f\"Work started at: {start}\")"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "fa05ba0e",
            "metadata": {},
            "source": [
                "## The `functools` Module\n",
                "\n",
                "The `functools` module provides higher-order functions that operate on or\n",
                "return other functions. Three particularly useful tools are `reduce`,\n",
                "`partial`, and `lru_cache`.\n"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "54599d7a",
            "metadata": {},
            "source": [
                "### `functools.reduce()`\n",
                "\n",
                "`reduce(function, iterable)` applies a two-argument function cumulatively\n",
                "to the items of an iterable, reducing it to a single value.\n",
                "Think of it as a fold: it combines elements left to right.\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "55e3bdb5",
            "metadata": {},
            "outputs": [],
            "source": [
                "from functools import reduce\n",
                "from itertools import chain\n",
                "\n",
                "# Sum all numbers (same as built-in sum, shown for illustration)\n",
                "total = reduce(lambda acc, x: acc + x, [1, 2, 3, 4, 5])\n",
                "print(total)    # 15\n",
                "\n",
                "# Product of all numbers\n",
                "product = reduce(lambda acc, x: acc * x, [1, 2, 3, 4, 5])\n",
                "print(product)  # 120\n",
                "\n",
                "# Flatten a list of lists\n",
                "nested = [[1, 2], [3, 4], [5, 6]]\n",
                "flat = reduce(lambda acc, x: acc + x, nested)\n",
                "print(flat)     # [1, 2, 3, 4, 5, 6]\n",
                "\n",
                "# In practice, prefer chain.from_iterable() or a nested comprehension for flattening.\n",
                "print(list(chain.from_iterable(nested)))\n",
                "print([item for group in nested for item in group])\n"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "8e9c7b1d",
            "metadata": {},
            "source": [
                "### `functools.partial()`\n",
                "\n",
                "`partial(function, *args, **kwargs)` returns a new function with some\n",
                "arguments pre-filled. This is called **partial application** \u2014 useful for\n",
                "creating specialized versions of general-purpose functions.\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "e111e046",
            "metadata": {},
            "outputs": [],
            "source": [
                "from functools import partial\n",
                "\n",
                "def power(base, exponent):\n",
                "    return base ** exponent\n",
                "\n",
                "square = partial(power, exponent=2)\n",
                "cube   = partial(power, exponent=3)\n",
                "\n",
                "print(square(4))   # 16\n",
                "print(cube(3))     # 27\n",
                "\n",
                "# Practical: pre-configure print with a separator\n",
                "import functools\n",
                "header = functools.partial(print, sep=' | ')\n",
                "header('Name', 'Score', 'Grade')  # Name | Score | Grade\n"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "ef85ae31",
            "metadata": {},
            "source": [
                "### `functools.lru_cache()`\n",
                "\n",
                "`@lru_cache` memoizes a function's results: the first time a function is\n",
                "called with given arguments, the result is stored. On subsequent calls with\n",
                "the same arguments, the cached result is returned immediately \u2014 no\n",
                "recomputation needed.\n",
                "\n",
                "LRU stands for **Least Recently Used**: when the cache is full, the least\n",
                "recently accessed entry is evicted.\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "8c30eb06",
            "metadata": {},
            "outputs": [],
            "source": [
                "from functools import lru_cache\n",
                "import time\n",
                "\n",
                "@lru_cache(maxsize=None)  # unlimited cache\n",
                "def fib(n):\n",
                "    if n <= 1:\n",
                "        return n\n",
                "    return fib(n - 1) + fib(n - 2)\n",
                "\n",
                "# Without cache, fib(40) would take seconds (2^40 calls)\n",
                "start = time.perf_counter()\n",
                "print(fib(50))   # 12586269025\n",
                "elapsed = time.perf_counter() - start\n",
                "print(f'Computed in {elapsed:.6f}s')  # microseconds with cache\n",
                "\n",
                "# Inspect cache statistics\n",
                "print(fib.cache_info())  # CacheInfo(hits=..., misses=51, maxsize=None, currsize=51)\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "9447548f",
            "metadata": {},
            "outputs": [],
            "source": [
                "### Exercise: functools\n",
                "#   1. Use reduce() to find the maximum value in [3, 1, 4, 1, 5, 9, 2, 6].\n",
                "#      (Hint: lambda acc, x: acc if acc > x else x)\n",
                "#   2. Use partial() to create `add10` \u2014 a function that adds 10 to any number.\n",
                "#      Test: add10(5) \u2192 15, add10(-3) \u2192 7.\n",
                "#   3. Decorate `count_ways(n)` below with @lru_cache to speed it up.\n",
                "#      count_ways(n) returns how many ways to climb n stairs (1 or 2 at a time).\n",
                "from functools import reduce, partial, lru_cache\n",
                "\n",
                "def count_ways(n):\n",
                "    if n <= 1: return 1\n",
                "    return count_ways(n - 1) + count_ways(n - 2)\n",
                "\n",
                "### Your code starts here.\n",
                "\n",
                "\n",
                "\n",
                "### Your code ends here.\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "id": "bf91dd14",
            "metadata": {},
            "outputs": [],
            "source": [
                "### Solution\n",
                "from functools import reduce, partial, lru_cache\n",
                "\n",
                "# 1. reduce to find max\n",
                "nums = [3, 1, 4, 1, 5, 9, 2, 6]\n",
                "maximum = reduce(lambda acc, x: acc if acc > x else x, nums)\n",
                "print(maximum)    # 9\n",
                "\n",
                "# 2. partial to create add10\n",
                "add = lambda a, b: a + b\n",
                "add10 = partial(add, 10)\n",
                "print(add10(5))   # 15\n",
                "print(add10(-3))  # 7\n",
                "\n",
                "# 3. lru_cache to speed up count_ways\n",
                "@lru_cache(maxsize=None)\n",
                "def count_ways(n):\n",
                "    if n <= 1: return 1\n",
                "    return count_ways(n - 1) + count_ways(n - 2)\n",
                "\n",
                "print(count_ways(30))  # 1346269 (fast with cache)\n"
            ]
        },
        {
            "cell_type": "markdown",
            "id": "a0ba9726",
            "metadata": {},
            "source": [
                "## Summary\n",
                "\n",
                "| Concept | Key idea |\n",
                "|---|---|\n",
                "| Lambda | Anonymous single-expression function: `lambda x: x ** 2` |\n",
                "| `map()` | Apply a function to every element: `map(f, iterable)` |\n",
                "| `filter()` | Keep elements where function returns `True` |\n",
                "| `sorted()` with key | Sort by custom criterion: `sorted(items, key=lambda x: x[1])` |\n",
                "| List comprehension | `[expr for item in seq if cond]` \u2014 concise list creation |\n",
                "| Dict comprehension | `{key_expr: value_expr for item in iterable}` \u2014 inline dict construction |\n",
                "| Set comprehension | `{expr for item in seq}` \u2014 inline set construction |\n",
                "| Decorator | Wraps a function to add behavior without modifying it; use `@name` |\n",
                "| `@functools.wraps` | Preserves the wrapped function's name and docstring |\n",
                "| Recursion | Function that calls itself; requires a base case + recursive case |\n",
                "| Context manager | `with` block that handles setup/teardown; `@contextmanager` for custom ones |"
            ]
        }
    ],
    "metadata": {
        "kernelspec": {
            "display_name": "Python 3 (ipykernel)",
            "language": "python",
            "name": "python3"
        },
        "language_info": {
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "file_extension": ".py",
            "mimetype": "text/x-python",
            "name": "python",
            "nbconvert_exporter": "python",
            "pygments_lexer": "ipython3",
            "version": "3.13.7"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 5
}