Circularity in Recursion

 

What is Circularity in Recursion?

In recursion, a function calls itself to solve a smaller version of a problem.
Circularity refers to this self-referential structure.

But — not all circularity is good.

To work properly, recursion must have:

1. A Base Case — a condition where recursion stops

2. A Recursive Case — where the function calls itself with a simpler input

If circularity exists without a base case, the recursion becomes infinite → ❌ stack overflow.

---

✔️ Good Circularity Example

Computing factorial of a number

def factorial(n):
    if n == 0:  # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

Let’s trace factorial(4):

factorial(4)
→ 4 * factorial(3)
→ 4 * 3 * factorial(2)
→ 4 * 3 * 2 * factorial(1)
→ 4 * 3 * 2 * 1 * factorial(0)
→ 4 * 3 * 2 * 1 * 1
→ 24

Each call reduces the problem (n decreases), eventually hitting the base case (0).

---

❌ Bad Circularity Example

Missing base case → infinite loop

def infinite_recursion():
    return infinite_recursion()

This function never stops calling itself and eventually crashes with:

RecursionError: maximum recursion depth exceeded

---

Why is Circularity Important?

Programmers often forget the base case or fail to make progress toward it.
We emphasize:

Good Circularity	Bad Circularity
Has a stopping condition	No base case
Moves toward base case	Problem never simplifies
Produces a result	Infinite recursion / crash