What is it

Two properties make up a recursive behavior:

1. Base case (terminal case)

   • terminating scenario (exit) that does not use recursion to produce an answer

2. Recursive step

   • a set of rules that reduces all successive cases towards the base case

# Person's ancestor

Base case: person's parent
Recursive: person's parent's ancestors

# Fib Sequence

Base case: fib(0) = 0
Recursive: fib(1) = 1

Fib(n) = Fib(n-1) + Fib(n-2)

Advantages

Because recursion relies on a native call stack, it makes unwinding easy.

Stack Size

Stack size is rarely an issue when you are dealing with logarithmic time complexities like binary search.

For example, one million records would be approximately take 20 recursive iteration depth. Billion records will approximately take 30 recursive iteration depth.

# n = 1,000,000 (million)
log2(1,000,000) ~= 20

# n = 1,000,000,000 (billion)
log2(1,00,000,000) ~= 30

In Python, a default stack size limit is 1000.

• Memory would become an issue first before a stack size limit.

Measuring Stack Size

# getting recursion limit
import sys

print(sys.getrecursionlimit())

# changing the recursion limit
sys.setrecursionlimit(1500)