AS Knowledge
← Back to Topics

Recursive Functions

Evaluating functions that are defined in terms of themselves.

Overview

A definition is recursive when it describes something in terms of itself. In computer science, recursion means a function or subroutine that calls itself. It is one of the most important ideas in programming: a recursive solution breaks a problem into smaller copies of the same problem, and keeps doing so until the pieces are small enough to answer directly.

In this ACSL category the emphasis is on mathematical recursive functions rather than full programs. A typical question gives you a function defined by cases and asks you to evaluate it for a specific input. The work is not hard, but it demands care: one arithmetic slip early on ruins everything that follows.

Key Concepts:

  • Recursive case: The rule that refers back to the function itself, usually with a smaller argument.
  • Base case: The rule that stops the recursion by giving a direct value. Without it the function would call itself forever.
  • Unwinding: Work down through the calls until a base case is reached, then work back up substituting the values you now know.

Key Concepts

Writing a Recursive Definition

Recursive functions are usually written as a set of cases. Each case has a condition on the input and a rule for that condition. Exactly one case should apply to any input.

The factorial function

n! = n × (n-1) × ... × 1, with 0! defined to be 1. Recursively:

f(x) = 1            if x = 0
f(x) = x * f(x-1)   if x > 0

The first line is the base case; the second is the recursive case. In Python:

def factorial(x):
    if x == 0:
        return 1
    return x * factorial(x - 1)
The Fibonacci numbers

0, 1, 1, 2, 3, 5, 8, 13, ... Each term is the sum of the two before it. The definition needs two base cases because the recursive rule looks back two steps:

f(N) = N                 if N ≤ 1
f(N) = f(N-1) + f(N-2)   if N > 1
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Kinds of Recursion

How to Evaluate by Hand

  1. Write the call you want, for example g(11).
  2. Decide which case applies (check the conditions in order) and write the right-hand side with the new call, for example g(11) = g(8) + 1.
  3. Repeat for each new call until you hit a base case that gives a plain number.
  4. Work back up the list, replacing each call with its value.
  5. For two-variable functions f(x, y), track both arguments on every line.

Examples

Example 1: Find g(11)
g(x) = g(x-3) + 1   if x > 0
g(x) = 3x           otherwise

Work down until the base case:

  1. g(11) = g(8) + 1
  2. g(8) = g(5) + 1
  3. g(5) = g(2) + 1
  4. g(2) = g(-1) + 1
  5. g(-1) = 3 × (-1) = -3 (base case, since -1 is not > 0)

Now work back up:

  1. g(2) = -3 + 1 = -2
  2. g(5) = -2 + 1 = -1
  3. g(8) = -1 + 1 = 0
  4. g(11) = 0 + 1 = 1

g(11) = 1

Example 2: Find h(13) with three cases
h(x) = h(x-7) + 1   when x > 5
h(x) = x            when 0 ≤ x ≤ 5
h(x) = h(x+3)       when x < 0
  1. h(13) = h(6) + 1 (top rule, 13 > 5)
  2. h(6) = h(-1) + 1 (top rule, 6 > 5)
  3. h(-1) = h(2) (bottom rule, -1 < 0)
  4. h(2) = 2 (middle rule)

Back up: h(-1) = 2, h(6) = 2 + 1 = 3, h(13) = 3 + 1 = 4.

h(13) = 4

Example 3: A two-variable function, f(12, 6)
f(x, y) = f(x-y, y-1) + 2   when x > y
f(x, y) = x + y             otherwise
  1. f(12, 6) = f(6, 5) + 2 (12 > 6)
  2. f(6, 5) = f(1, 4) + 2 (6 > 5)
  3. f(1, 4) = 1 + 4 = 5 (1 is not > 4)

Back up: f(6, 5) = 5 + 2 = 7, f(12, 6) = 7 + 2 = 9.

f(12, 6) = 9

Example 4: A recursive procedure

Consider this algorithm for painting a square: if the side is less than 2 feet, stop. Otherwise divide the square into 4 equal squares, paint one of them, and repeat the procedure on each of the other three. If we start with a 16-foot square (area 256), how much is painted?

  1. Side 16 → four squares of side 8. Paint 1: area 64. Three remain.
  2. Each side-8 square → four of side 4. Paint 3 total: area 3 × 16 = 48. Nine remain.
  3. Each side-4 square → four of side 2. Paint 9 total: area 9 × 4 = 36. Twenty-seven remain.
  4. Each side-2 square → four of side 1. Paint 27 total: area 27 × 1 = 27. Side 1 is less than 2, so stop.

Total painted: 64 + 48 + 36 + 27 = 175 square feet

Practice Problems

Problem 1 Junior

Find f(7) given the following definition:

f(x) = f(x-2) + 3   if x > 0
f(x) = x            otherwise

Problem 2 Junior

Find g(13) given the following definition:

g(x) = g(x-4) + x   if x > 3
g(x) = 2x           if x ≤ 3

Problem 3 Intermediate

Find h(19) given the following definition:

h(x) = h(x-7) + 2   when x > 4
h(x) = x            when 0 ≤ x ≤ 4
h(x) = h(x+3)       when x < 0

Problem 4 Intermediate

Find f(20, 3) given the following definition:

f(x, y) = f(x-y, y+1) + 3   when x > y
f(x, y) = x * y             otherwise

Problem 5 Senior

Find f(8) given the following definition:

f(x) = f(x-1) + f(x-3)   if x > 2
f(x) = x                 if x ≤ 2