Class 12 Functions and Recursion: Complete Concepts and Practice

Big picture

A function is a named block of code that performs a task and can be reused. Functions make programs shorter, easier to read and easier to test. Board questions ask you to write functions, predict outputs involving default arguments and scope, and spot errors.

Recursion is a function calling itself to solve a smaller version of the same problem. It is elegant for problems like factorial, Fibonacci and sum of digits, but it needs a correct base case to stop.

Learning goals

• Distinguish built-in, module and user-defined functions.

• Define and call functions with positional, default and keyword arguments.

• Return single and multiple values.

• Explain the flow of execution in a program with functions.

• Explain local and global scope and use the global keyword.

• Explain how mutable and immutable objects behave when passed to functions.

• Write and trace recursive functions, and compare recursion with iteration.

Core ideas

1. Types of functions

2. Defining and calling a function

def area(l, b=2):          # function header; l and b are parameters
    return l * b           # function body

print(area(5))             # 10   (b takes its default value 2)
print(area(5, 3))          # 15   (positional arguments)
print(area(b=4, l=3))      # 12   (keyword arguments, any order)

• Parameters are the names in the function definition; arguments are the values passed in the call.

• Positional arguments are matched by position.

• Default parameters take a value if no argument is given. Default parameters must come after non-default ones: def f(a=1, b) is a SyntaxError.

• Keyword arguments are matched by name, so their order doesn't matter. After a keyword argument, you can't give a positional one: area(l=3, 4) is an error.

Mixed example: def h(a, b=3, c=4): return a + b * c; then h(2, c=1) gives 2 + 3 × 1 = 5.

3. Returning values

A function without return (or with a bare return) returns None. A function can return several values, which are packed into a tuple:

def stats(a, b):
    return a + b, a * b

s, p = stats(3, 4)
print(s, p)          # 7 12
print(stats(3, 4))   # (7, 12)

4. Flow of execution

Python executes statements from top to bottom. A def statement only defines the function; its body runs only when the function is called. When a call is made, control jumps to the function, executes its body, and returns to the point after the call.

5. Scope of variables

• A local variable is created inside a function and exists only while the function runs.

• A global variable is created outside all functions and can be read anywhere.

• Assigning to a name inside a function creates a new local variable, unless the name is declared global.

x = 10

def f():
    x = 5            # a new local x
    print(x, end=' ')

f()
print(x)             # prints: 5 10

def g():
    global x         # refer to the global x
    x += 1

g()
print(x)             # 11

Without the global statement, x += 1 inside g() would raise UnboundLocalError, because Python treats x as local but it has no value yet. Python searches names in the order Local, Enclosing, Global, Built-in (LEGB).

6. Passing mutable and immutable objects

Python passes a reference to the object. What happens depends on whether the object can change:

def change(L):
    L.append(9)      # changes the same list object

M = [1]
change(M)
print(M)             # [1, 9]

def change2(n):
    n += 1           # creates a new int; the caller's variable is unaffected

k = 5
change2(k)
print(k)             # 5

Mutable objects (lists, dictionaries) can be modified inside a function, and the change is visible outside. Immutable objects (int, float, str, tuple) can't be changed in place, so the caller's value stays the same.

7. Recursion

A recursive function calls itself. Every recursive function needs:

1. a base case, which returns without a recursive call; and

2. a recursive case, which calls the function on a smaller problem that moves towards the base case.

Without a base case, the calls never stop, and Python raises RecursionError: maximum recursion depth exceeded.

Classic examples (tested):

def fact(n):                      # n! = n × (n-1)!
    if n <= 1:
        return 1                  # base case
    return n * fact(n - 1)
print(fact(5))                    # 120

def fib(n):                       # 0, 1, 1, 2, 3, 5, 8, 13 ...
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
print([fib(i) for i in range(8)]) # [0, 1, 1, 2, 3, 5, 8, 13]

def sum_digits(n):
    if n == 0:
        return 0
    return n % 10 + sum_digits(n // 10)
print(sum_digits(1234))           # 10

def power(a, b):
    if b == 0:
        return 1
    return a * power(a, b - 1)
print(power(2, 5))                # 32

Tracing fact(3): fact(3) = 3 × fact(2) = 3 × (2 × fact(1)) = 3 × 2 × 1 = 6. Each call waits on the call stack until the call below it returns.

Order of printing in recursion:

def p(n):
    if n == 0:
        return
    print(n, end=' ')   # print BEFORE the recursive call
    p(n - 1)
p(3)                    # 3 2 1

def q(n):
    if n == 0:
        return
    q(n - 1)
    print(n, end=' ')   # print AFTER the recursive call
q(3)                    # 1 2 3

Recursion and iteration compared

A reliable routine for function questions

1. Match each argument to its parameter: positional first, then keyword, then defaults.

2. For scope, check whether a name is assigned inside the function; if it is, and there is no global, it's local.

3. For mutable arguments, check whether the function changes the object in place or rebinds the name.

4. For recursion, write the calls down the page until the base case, then return values up the page.

Connections that matter

• Advanced Python revision covers data types and mutability used here.

• Exception handling catches errors such as RecursionError and TypeError in functions.

• Stack data structure: recursion uses the call stack, and stacks are implemented with functions like push() and pop().

Common mistakes

• Putting a default parameter before a non-default one.

• Forgetting `return` and getting None.

• Changing a global variable without declaring it `global`.

• Writing recursion without a base case, or with a recursive call that doesn't move towards it.

• Thinking an integer argument changed inside a function changes the caller's variable.

Revision checklist

• I can write functions with positional, default and keyword arguments.

• I can return multiple values and unpack them.

• I can explain local and global scope and use global.

• I can predict the effect of passing lists versus integers.

• I can write and trace recursive functions with correct base cases.