Skip to main content

Define recursion; direct vs indirect

Short answer

Recursion is a process where a function calls itself directly or indirectly until a base case. Direct example: sum(n)=n+sum(n-1) with sum(0)=0. Indirect example: isOdd calls isEven, and isEven calls isOdd, forming an A->B->A cycle.

Define recursion. What do you mean by direct and indirect recursion? Explain with example.

Recursion is the process in which a function calls itself, directly or indirectly, to solve a problem by reducing it to smaller instances until a base case is reached.

Direct recursion

A function calls itself in its own body.

int sum(int n) {
    if (n == 0) return 0;          /* base case */
    return n + sum(n - 1);         /* sum calls sum */
}

sum(3) = 3 + sum(2) = 3 + 2 + sum(1) = 6. Chain: sum → sum → sum.

Indirect recursion

A function calls another function that eventually calls the first one (cycle A → B → A).

int isEven(int n);
int isOdd(int n)  { return n == 0 ? 0 : isEven(n - 1); }
int isEven(int n) { return n == 0 ? 1 : isOdd(n - 1); }

isEven(2) → isOdd(1) → isEven(0) → returns 1. Chain: isEven → isOdd → isEven.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 5 questions →