Recursion

What is recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem, until it reaches a simple base case that stops the chain. It’s the natural way to process anything tree-shaped — which, in mobile, includes your entire view hierarchy and JSON data.

The two essential parts

• Base case — the condition where it stops (no more recursion).
• Recursive case — the function calls itself on a smaller input, moving toward the base case.

fun factorial(n: Int): Int {
    if (n <= 1) return 1            // base case
    return n * factorial(n - 1)     // recursive case
}
// factorial(4) = 4*3*2*1 = 24

Recursion shines on trees

Counting all views in a layout, summing sizes of files in nested folders, or walking nested JSON are all elegant with recursion:

// count every view in a hierarchy (a tree)
fun countViews(view: View): Int {
    if (view !is ViewGroup) return 1            // base: a leaf view
    var total = 1
    for (i in 0 until view.childCount) {
        total += countViews(view.getChildAt(i)) // recurse into children
    }
    return total
}

The danger: stack overflow

Every recursive call uses a frame on the call stack, which is limited. Recurse too deeply — thousands of levels, or forgetting the base case — and the app crashes with a StackOverflowError. On mobile, with smaller stacks and unpredictable data (a deeply nested API response), this is a real risk.

// BUG: no base case -> infinite recursion -> crash
fun broken(n: Int): Int = broken(n - 1)

Recursion vs iteration

Any recursion can be rewritten as a loop (often using an explicit stack/queue). Recursion is cleaner for tree problems; iteration avoids stack-depth risk for very deep or large inputs. On mobile, prefer iteration when depth could be large or attacker/data-controlled.

Beware repeated work (use memoization)

Naive recursion can recompute the same sub-problem many times (classic Fibonacci is exponential!). Memoization — caching results in a map — turns it linear. This is the bridge to dynamic programming.

val memo = HashMap<Int, Long>()
fun fib(n: Int): Long = memo.getOrPut(n) {
    if (n < 2) n.toLong() else fib(n - 1) + fib(n - 2)
}

Common mistakes

• Forgetting or mis-writing the base case (infinite recursion → crash).
• Deep recursion on large/unknown data (stack overflow) — use iteration.
• Re-computing sub-problems instead of memoizing.

Summary: Recursion solves a problem via smaller copies of itself, with a base case to stop. It’s ideal for trees (view hierarchy, nested JSON), but each call uses stack space — guard against deep recursion (stack overflow) and memoize to avoid repeated work.