Functions and Recursion in Python

Posted on

Algorithms are built from functions. Once you can package logic into a named function and call it, including calling it from within itself, you can express nearly any algorithm in this course.

Defining a function#

1def add(a, b):
2    return a + b
3
4print(add(2, 3))   # 5

A function takes parameters, does work, and usually returns a value with return. If there is no return, the function returns None.

Default and keyword arguments#

1def greet(name, greeting="Hello"):
2    return f"{greeting}, {name}"
3
4print(greet("Ana"))                 # 'Hello, Ana'
5print(greet("Ben", greeting="Hi"))  # 'Hi, Ben'

Defaults let callers skip arguments. Keyword arguments make calls readable.

Returning multiple values#

Python returns multiple values as a tuple, which you can unpack:

1def min_max(nums):
2    return min(nums), max(nums)
3
4low, high = min_max([4, 1, 7])
5print(low, high)   # 1 7

Recursion: a function that calls itself#

Recursion solves a problem by reducing it to a smaller version of the same problem. Every recursive function needs two parts:

  1. A base case that stops the recursion.
  2. A recursive case that moves toward the base case.

Classic example, factorial:

1def factorial(n):
2    if n <= 1:        # base case
3        return 1
4    return n * factorial(n - 1)  # recursive case
5
6print(factorial(5))  # 120

Trace it: factorial(3) calls factorial(2) calls factorial(1), which returns 1, then the results multiply back up: 1, 2, 6.

The call stack#

Each recursive call is pushed onto the call stack and waits for the inner call to finish. Miss the base case and you get infinite recursion:

1# Python raises RecursionError instead of crashing:
2def broken(n):
3    return broken(n - 1)   # no base case, do not run this

Understanding the stack is essential for tree and graph algorithms later in the main lessons.

Recursion vs iteration#

Anything recursive can be written with a loop, and vice versa. Recursion is often cleaner for problems that split naturally, like trees:

1def fib(n):
2    if n < 2:            # base cases: fib(0)=0, fib(1)=1
3        return n
4    return fib(n - 1) + fib(n - 2)
5
6print([fib(i) for i in range(7)])  # [0, 1, 1, 2, 3, 5, 8]

This naive fib is elegant but slow (it recomputes the same values). Fixing that with memoization is a core technique you will meet in the curriculum. Keep the Big-O cheat sheet handy to reason about recursive costs.

Next: classes and OOP, where you build your own data structures.