Unit 4: Functions and recursion

I. Orientation: The Function as Python's Unit of Abstraction

A function is a named sequence of statements that performs a computation and is executed only when called. Python has supported def since its first public release (Guido van Rossum, 1991), and the language ships with two supplies of ready-made functions: built-ins that are always available (len, int, print), and library functions that must be imported (math.sqrt). Everything in this unit rests on the distinction between using a function and defining one.

• Definition vs. call: def creates a function object and binds it to a name; it executes nothing. Only f(...) runs the body.
• Fruitful vs. void functions: a fruitful function ends with a return expression (math.sqrt(9) → 3.0); a void function returns the special object None (print("hi") → None).
• Functions are first-class objects: type(len) → <class 'builtin_function_or_method'>; a function name without parentheses is a value that can be assigned or passed as an argument.
• Each call gets a fresh namespace: a frame holding that call's local variables is pushed on the call stack and destroyed on return.
• Conventions: snake_case names, a triple-quoted docstring as the first statement, and 4-space indentation for the body.

II. Calling Existing Functions — the caller's view

Every use of a function is an expression whose value replaces the call. Python evaluates the argument expressions first, binds them to parameters, runs the body, and substitutes the returned value at the call site.

A. function calls

A call consists of a function-valued expression followed by a parenthesised, comma-separated argument list.

• Syntax: name(arg1, arg2). The parentheses are what trigger execution: len is a value, len("abc") is a call returning 3.
• Return value must be captured or used: n = len(word) keeps the result; writing len(word) alone as a statement computes and discards it.
• Dotted calls: math.sqrt(2) names the module, then the attribute; "abc".upper() calls a method on an object.
• Import forms: import math requires the prefix; from math import sqrt puts sqrt in the current namespace.
• Composition: a call may appear wherever an expression may, so calls nest: int(math.sqrt(float(x))) evaluates innermost-first.
• Arity errors are immediate: math.sqrt(4, 5) raises TypeError: sqrt expected 1 argument, got 2.

B. type conversion and coercion

Python is strongly typed, so values change type only by explicit conversion or by the narrow set of implicit numeric promotions.

1. Explicit conversion (type casting): the type names act as functions returning a new object.
   • int("42") → 42; int(3.9) → 3 (truncates toward zero, never rounds); int("3.9") → ValueError.
   • float(7) → 7.0; str(3.0) → '3.0'; bool(0), bool(""), bool([]) → False.
   • int("ff", 16) → 255 shows the optional base parameter.
2. Implicit coercion (mixed-mode arithmetic): where operand types differ, Python widens along the chain bool → int → float → complex.
   • 1 + 2.0 → 3.0; True + 1 → 2, because bool is a subclass of int.
   • 7 / 2 → 3.5: true division always yields float, even for two int operands; 7 // 2 → 3 keeps int.
   • Coercion stops at numbers. "3" + 4 raises TypeError: can only concatenate str (not "int") to str — deliberate, since Perl/JavaScript-style silent stringification hides bugs.

C. math functions

The math module wraps the C library's double-precision routines, so its results are float and its domain errors are exceptions rather than NaN.

import math
math.sqrt(25)        # 5.0
math.pow(2, 10)      # 1024.0   (float, unlike 2 ** 10 -> 1024)
math.log(math.e)     # 1.0      natural log
math.log(1000, 10)   # 2.9999999999999996  (base as 2nd argument)
math.log10(1000)     # 3.0      more accurate for base 10
math.sin(math.pi/2)  # 1.0      argument in RADIANS
math.factorial(5)    # 120
math.floor(-2.3)     # -3       ; math.ceil(-2.3) -> -2

• Constants: math.pi ≈ 3.141592653589793, math.e ≈ 2.718281828459045, math.inf, math.nan.
• Angles: trigonometric functions take and return radians; convert with math.radians(180) → 3.14159... and math.degrees(math.pi) → 180.0.
• Domain errors: math.sqrt(-1) and math.log(0) raise ValueError; use cmath.sqrt(-1) → 1j for complex results.
• Floating-point limits: math.sqrt(2) ** 2 → 2.0000000000000004; compare with math.isclose(a, b), never ==.
• Related built-ins: abs, round, min, max, sum need no import. Note round(2.5) → 2 (round-half-to-even).

III. Writing Your Own Functions — the definer's view

New functions exist to name a computation, remove duplication, and isolate debugging. A well-chosen function turns a long script into a short sequence of readable calls.

A. adding new function

A definition is a compound statement: a header ending in a colon, then an indented body.

def circle_area(radius):
    """Return the area of a circle of the given radius."""
    return math.pi * radius ** 2

• Header: the keyword def, the function name, a parenthesised parameter list, a colon.
• Body: indented consistently; may contain any statements, including further definitions and calls.
• Definition must precede the call in execution order, not in file order — a function may call another defined later, provided both definitions have run before the first call.
• return ends the call immediately, handing its value back; a bare return, or falling off the end, yields None.
• Placeholder bodies: pass satisfies the requirement for a non-empty body during incremental development.
• Refactoring gain: replacing three near-identical blocks with one function reduces the number of places a bug can hide from three to one.

B. parameters and argument

A parameter is the name in the definition's header; an argument is the value supplied at the call. Binding an argument to a parameter is an assignment inside the new frame.

• Positional arguments: matched left to right — pow(2, 3) ≠ pow(3, 2).
• Keyword arguments: matched by name, so order is free: print("a", "b", sep="-", end="").
• Default values: def greet(name, greeting="Hello"): makes greeting optional; defaults must follow non-default parameters.
• Defaults are evaluated once, at definition time: def f(items=[]) shares one list across all calls; use def f(items=None) and set items = [] in the body.
• Variable arity: *args collects surplus positional arguments into a tuple, **kwargs collects surplus keyword arguments into a dict; parameters after a bare * are keyword-only.
• Argument passing is by object reference: rebinding a parameter (x = x + 1) cannot affect the caller, but mutating a passed object (lst.append(1)) is visible to the caller.
• Scope: parameters and other names assigned in the body are local and vanish on return; reading follows the LEGB order (Local, Enclosing, Global, Built-in), and global/nonlocal are required to rebind an outer name.

IV. Recursion

Recursion solves a problem by expressing it in terms of a smaller instance of the same problem. Because each call has its own frame, the interpreter keeps the partly finished calls stacked until the smallest instance is reached.

A. recursion and its use

A correct recursive function needs a base case that returns without recursing and a recursive case that moves strictly toward it.

def factorial(n):
    if n <= 1:            # base case
        return 1
    return n * factorial(n - 1)   # recursive case

• Trace of factorial(3): frames stack as factorial(3) → factorial(2) → factorial(1); the innermost returns 1, then 2*1 = 2, then 3*2 = 6.
• Naturally recursive definitions: fib(n) = fib(n-1) + fib(n-2) with fib(0)=0, fib(1)=1; gcd(a, b) = gcd(b, a % b) with base b == 0.
• Divide and conquer: binary search discards half the list per call, giving O(log n); merge sort splits, sorts halves, and merges in O(n log n).
• Recursively defined data: traversing directory trees, nested lists, JSON, or the nodes of a binary tree, where the sub-structure has the same shape as the whole.
• Classic illustration: Towers of Hanoi — move n-1 discs aside, move the largest, move n-1 back — requiring exactly 2**n - 1 moves.
• Missing or unreachable base case produces RecursionError: maximum recursion depth exceeded, the runtime signature of infinite recursion.

B. Cost, depth limits and the iterative alternative

Recursion buys clarity at the price of stack space, so the choice between the two forms is an engineering decision.

1. Recursion: mirrors the mathematical definition and needs no explicit bookkeeping, but every pending call holds a frame. CPython caps depth at sys.getrecursionlimit() (1000 by default) and performs no tail-call optimisation, so linear recursion over a 10,000-element list fails.
2. Iteration: a loop with an accumulator (for i in range(2, n+1): result *= i) uses constant space and runs faster, at the cost of making the invariant less obvious.

• Overlapping subproblems: naive fib(n) makes calls exponential in n (≈ 1.6**n); @functools.lru_cache memoises results and reduces it to O(n).
• Rule of thumb: prefer recursion when the data is recursive (trees, nested structures) and iteration when the recursion is merely a countdown over a linear range.