Mutual recursion on complementary predicates

Intermediate Recursion & structural decomposition

Created by Pavel · 29.04.2026 at 19:04 UTC

Mutual recursion means two (or more) functions call each other. The textbook example is even and odd on natural numbers: even(n) is true if n==0, else odd(n-1); odd(n) is false if n==0, else even(n-1). The structure alternates—each function delegates to its partner on a strictly smaller argument.

In parsing and validation, mutual recursion shows up between grammar rules (“expression” calls “term”, “term” calls “factor”, “factor” may call “expression” again inside parentheses). For data scientists the full grammar machinery is overkill, but the pattern appears whenever two complementary shape predicates bounce between each other.

You still need ordinary base cases on both sides; mutual recursion does not remove the obligation to terminate.

PEP 8 (readability): [1].

Sources

[1]https://peps.python.org/pep-0008/Return to text

University approvals: 0

Tasks

Question 1

Mutual recursion is most natural when:

Hint

Alternating roles → alternating functions.

You need faster NumPy dot products

Two predicates alternate on structure (e.g. even/odd, nested JSON “object vs array” validators)

You import TensorFlow

You must avoid all function calls

Question 2

Compared with a single recursive function with an extra mode parameter, splitting into two mutual functions mainly:

Hint

Design clarity vs one function with flags.

Guarantees O(1) memory

Can mirror alternating rules more directly at the cost of two entry points

Prevents all RecursionError

Is required by the Python grammar

Question 3

Implement parity_even(n) and parity_odd(n) for n >= 0 without % or // division tricks: parity_even(0) is True; otherwise parity_even(n) defers to parity_odd(n-1). Symmetric definition for odd.

Hint

Decrement n and cross-call; both need n==0 bases.

def parity_even(n: int) -> bool:
    pass


def parity_odd(n: int) -> bool:
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Recursion & structural decomposition
Difficulty: Intermediate
Completed: 0 users

Creator

Pavel