<aside> 💡 Method defined in terms of itself

</aside>

Recurrence Ratio

It’s a (in)equation that describes a function based on itself, considering smaller inputs.

Analysis

1. Establish the recurrence ratio.
2. Expand the execution tree based on its recurrence ratio.
3. Determine the top of the tree (highest point).
4. Sum the cost of every execution level.
5. Sum the total cost (every level).

Top of the tree

The height is the longest path from the root to the top.

<aside> 💡 n - 1

</aside>

How does it work?

The method must have a base case or a “stopping point” that tells it when it should stop calling itself. Otherwise, it’s going to go into an infinite loop.

It usually works by calling itself adding or subtracting X from a counter until it reaches the base case.