Course contentsShow
← Computer Science
Lesson 875 of 2,87220. Recursion Patterns and TechniquesFree lesson

Mutual Recursion

Solve problems where two or more functions call each other recursively, like parsing or state machines.

Mutual Recursion

You'll learn how two or more functions can call each other in a recursive cycle to solve interrelated problems.

Core Idea

Mutual recursion occurs when function A calls function B, and function B calls function A (or involves more functions in a chain). Unlike standard recursion where a function calls itself, mutual recursion distributes the problem across multiple functions that rely on each other.

Think of it like a relay race: Runner A passes the baton to Runner B, who eventually passes it back to Runner A. Each runner handles their portion of the track, but they depend on each other to complete the race.

Common Use Cases

Even/Odd Checking: One classic example determines if a number is even or odd:

  • isEven(n) checks if n is zero (base case: true), otherwise calls isOdd(n-1)
  • isOdd(n) checks if n is zero (base case: false), otherwise calls isEven(n-1)

State Machines: When a system alternates between different states, each state can be a function that transitions to another state-function based on input.

Parsing: When parsing nested structures (like expressions or grammar rules), different parsing functions handle different syntax elements and call each other as they encounter nested patterns.

Why Use It?

Mutual recursion naturally models problems where:

  • Different states or conditions require different logic
  • The problem structure alternates between distinct phases
  • You want to separate concerns while maintaining recursive flow

Critical Requirements

Like standard recursion, mutual recursion must have base cases in at least one function to prevent infinite loops. Each function must eventually reach a condition that stops calling back and forth.

Key Takeaway: Mutual recursion lets you solve problems by breaking them into interdependent functions that call each other recursively, naturally expressing alternating states or phases in your problem.