Let’s talk about Recursion | Kyaw Zay Ya Lin Tun

Introduction

Recursion is something most programmers have at least heard of. When I first started programming, I didn’t really understand it — I’d see a recursive call and immediately feel lost. It took me a good amount of time and deliberate practice before it finally clicked. I’m writing this to help others avoid going through the same struggle, so I’ll try to explain recursion in the clearest, most approachable way I can.

What is recursion?

Recursion is when a function calls itself. Simply put:

func foo() {
  print("foo() called")
  foo() // calling itself, hence, recursion
}

When foo calls itself like this, it keeps printing the same line endlessly. You can achieve the same infinite output without recursion using a while loop:

while true {
  print("yoo")
}

But say you don’t want infinite output — you just want to print the numbers 1 through 5 in order. You’d use a for loop (you could use while too, but let’s go with for here):

for i in 1 ... 5 {
  print(i) // Will print 1, 2, 3, 4, 5
}

From this, you can understand that any loop can be rewritten using recursion. Let’s rewrite that for loop recursively:

func foo(_ i: Int = 1) {
  if i > 5 { return }
  print(i)
  foo(i + 1)
}

foo()

Alt Text
If that code felt confusing, take your time with the next section and read it carefully — it’ll be worth it.

Functions are stored on the stack when they’re being executed. We covered stacks in a previous article — they follow last-in, first-out (LIFO) order. The last thing pushed in is the first thing to come out.

Let’s visualize how functions get stored on the stack:

func a() {
  b()
  print("A")
}

func b() {
  c()
  print("B")
}

func c() {
  d()
  print("C")
}

func d() {
  print("D")
}

func main() {
  a()
}

Treat main as the entry point. What do you think gets printed when you run this? "ABCD"? The actual output is "DCBA". Let’s see why.

First, main calls a, so a gets pushed onto the stack. When I say “pushed”, I mean a full stack frame is created — including the return address, any passed-in parameters, and local variables. For simplicity, I’ll just write the function names from here on.

main() is calling a()

|   |
+---+
| a | <- push a
+---+

Inside a, b is called before print("A"), so since code runs line by line, we can’t print "A" yet. We need to call b first:

|   |
+---+
| b | <- push b
+---+
| a | TODO: print("A")
+---+

b calls c before printing, so the same thing happens:

|   |
+---+
| c | <- push c
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

Then c calls d:

|   |
+---+
| d | <- push d
+---+
| c | TODO: print("C")
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

d doesn’t call anything else, so nothing more gets pushed. This is where the stack starts popping. The top frame d is popped and executed — print("D") runs first:

> Pop d from stack, and execute

|   |
+---+
| c | TODO: print("C")
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
+---------------------------+

The stack still has c, b, and a. They keep getting popped one by one until the stack is empty:

> Pop c from stack, and execute

|   |
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
| C                         |
+---------------------------+

> Pop b from stack, and execute

|   |
+---+
| a | TODO: print("A")
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
| C                         |
| B                         | 
+---------------------------+

> Pop a from stack, and execute

|   | 
|   | 
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
| C                         |
| B                         | 
| A                         |
+---------------------------+

After "A" is printed, the stack is empty. There’s nothing left in a() or main(), so the program exits.

This way of visualizing function calls is called a recursive stack. Visualization is crucial for understanding recursion. As you read this article, try drawing the recursive stack alongside it — trace each function being pushed in, then popped back out, one by one.

Once you have the recursive stack down, let’s look at the recursive tree. Knowing tree data structures helps, but since trees are also best understood through recursion, it’s a bit of a chicken-and-egg situation. I’ll do my best to make it approachable.

The recursive stack and the recursive tree are really just two different ways to visualize the same concept.

If we view the stack frames from above as a tree, it looks like this:

  f(a)
  / 
f(b)
  \
  f(c)
  /
f(d)

f(a) calls f(b), which calls f(c), which calls f(d). Once we hit the bottom, we unwind back up through the stack, like this:

f(a)<----+ print("A")
  /      |
f(b)<----+ print("B")
  \      |
  f(c)<--+ print("C")
  /      |
f(d)-----+ print("D")

After reaching the deepest leaf node, we travel back up to the parent. This is called backtracking — we’ll cover it in detail later.

If this makes sense, let’s do a quick check. Here’s the code slightly modified:

func a() {
  print("A")  
  b()
}

func b() {
  print("B")
  c()
}

func c() {
  print("C")
  d()
}

func d() {
  print("D")
}

func main() {
  a()
}

Does this print "ABCD" or "DCBA"? Why? Try drawing the recursive stack and recursive tree yourself and do a dry run. If you’re unsure, copy the code and run it. Then set some breakpoints and step through it line by line.

Also try drawing the recursive stack/tree for the foo function from earlier.

By now, you should be starting to see recursion more clearly in your mind.

Recursion in Action

There are two fundamental requirements for writing any recursive function:

A base case — a condition that tells the recursion when to stop.
A subproblem — the original problem broken down into smaller pieces that can be solved incrementally.

In the a, b, c, d example, the recursion stops when it reaches d. In the foo function that prints 1 through 5:

func foo(_ i: Int = 1) {
  if i > 5 { return }
  print(i)
  foo(i + 1)
}

The if i > 5 { return } line is the base case. Once i hits 6, 7, and so on, the recursive stack unwinds. Without a base case, you get a stack overflow — not the website, but the actual error where functions keep piling onto the stack without end until the computer runs out of stack memory. (That’s actually where the website got its name.)

Let’s explore the idea of breaking a problem into subproblems with the classic factorial example. The formula is:

n! = n x (n - 1) x (n - 2) x ... 1

For example, five factorial (5!):

5! = 5 x 4 x 3 x 2 x 1
   = 120

Instead of computing the whole thing at once, we can break it down:

5! = 5 x 4!

And 4! is just:

4! = 4 x 3!

Expanding it fully:

5! = 5 x 4!
     |   |
     |   4 x 3!
     |   |   |
     |   |   3 x 2!
     |   |   |   |
     |   |   |   2 x 1!
     |   |   |   |   |
     5 x 4 x 3 x 2 x 1

The base case: mathematically, 0! = 1 and 1! = 1. So our base case is n == 0 || n == 1.

With both requirements identified, let’s write the function. Start with the shell:

func factorial(of n: Int) -> Int {
}

Always write the base case first, before any other logic. This is important — remember it. The rest of the recursion will take care of itself.

func factorial(of n: Int) -> Int {
  if n == 0 || n == 1 {
    return 1
  }
}

Breaking the big problem into a smaller one gives us:

n! = n x (n - 1)!

This is also called the recurrence relation. Translating it to code:

func factorial(of n: Int) -> Int {
  if n == 0 || n == 1 {
    return 1
  }
  
  return n * factorial(of: n - 1)
}

Run this and you’ll see it correctly computes factorials.

Here’s the recursive tree for 5!. Try drawing the recursive stack on your own — it’s good practice. I personally find the recursive tree more intuitive, so I’ll keep using that going forward.

              f(5) [n = 5]
               /
         5 * f(4)
                \
             4 * f(3)
                 /
             3 * f(2)
                  \
             2 * f(1)
                  /
                 1

When f(1) is reached, the base case kicks in and returns 1. From there, each resolved value propagates back up, multiplying along the way until we get the final result of 5!.

Now that you understand that, let’s tackle Fibonacci numbers. If you don’t remember how Fibonacci works, look it up — it’s straightforward. The formula is:

let the nths fibonacci number be f(n),

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

So for the 5th Fibonacci number:

f(5) = f(4) + f(3)

Base cases: f(0) = 0, f(1) = 1, so when n is 0 or 1, return n.

Writing the base case first:

func fib(of n: Int) -> Int {
  if n <= 1 { // n == 0 || n == 1
    return n
  }
}

Then plug in the formula:

func fib(of n: Int) -> Int {
  if n <= 1 { // base case: n == 0 or n == 1
    return n
  }
  
  return fib(of: n - 1) + fib(of: n - 2)
}

Let’s draw the recursive tree:

              f(5)
              /  \
           f(4) + f(3)
            / \
        f(3) + f(2)
        / \
    f(2) + f(1)
    / \
f(1) + f(0)

Starting from the top, f(5) with n = 5 isn’t a base case, so it becomes f(4) + f(3). Since code reads left to right, we need to resolve f(4) before we can add f(3). So we go left first:

f(4) → f(3) + f(2) → again, resolve f(3) first → f(2) + f(1) → resolve f(2) → f(1) + f(0). Now we’ve hit base cases:

f(1) = 1
f(0) = 0
f(2) = f(1) + f(0)
     = 1 + 0
     = 1

With f(2) resolved, the tree looks like:

              f(5)
              /  \
           f(4) + f(3)
            / \
        f(3) + f(2)
        / \
       1 + f(1)

f(1) is a base case = 1, so:

f(3) = 1 + f(1)
     = 1 + 1
     = 2

Tree now:

              f(5)
              /  \
           f(4) + f(3)
            / \
           2 + f(2)

f(2) isn’t a base case, so we branch again:

              f(5)
              /  \
           f(4) + f(3)
            / \
           2 + f(2)
               /  \
            f(1) + f(0)

f(1) = 1, f(0) = 0, so f(2) = 1. That gives us:

f(4) = 2 + 1
     = 3

Tree:

              f(5)
              /  \
             3 + f(3)

We know f(3) = 2 from earlier, but the computer doesn’t — it has to recompute it. I’ll skip drawing that branch out again, but the final result is:

              f(5)
              / \
             3 + 2

So f(5) = 5.

This algorithm can actually be optimized. We computed f(2) and f(3) multiple times. One way to avoid this is to cache results as you go — if a value has already been computed, return the cached version instead of recomputing. This is called memoization. We won’t go into it here, but it’s good to be aware of.

At this point, you should have a solid enough understanding of recursion to follow along, even if you can’t write recursive logic from scratch just yet.

Thinking in recursion

Now that we’ve worked through those examples, let’s look at how to write recursive functions on your own.

We said there are two fundamental requirements:

The base case — when does the recursion end?
How do you break the problem into subproblems, and how do you combine the results?

Beyond those two, there are two more things to think about:

What should the function return?
What should it accept as parameters?

The return value typically carries intermediate values — information that a child recursive frame passes back up to its parent. Looking at the Fibonacci example:

              f(5)
              /  \
           f(4) + f(3)
            / \
        f(3) + f(2)
        / \
    f(2) + f(1)
    / \
f(1) + f(0)

The leaf nodes at the bottom are f(1) and f(0). Their parent is f(2). For f(2) to compute its result, its children f(1) and f(0) need to return their values. Those returned values are the intermediate values that get passed up the tree. By returning them, each node contributes a piece toward the final answer.

Read that again if it didn’t click — it’s an important concept.

Now let’s talk about parameters. We’ll use a new version of a familiar problem: reversing an integer array.

Given [1, 2, 3, 4, 5], return [5, 4, 3, 2, 1].

The base case: stop when the array is empty.

if arr.isEmpty { return }

Breaking the problem into subproblems: take the last element, then recursively reverse everything else.

reverse(arr) = [last element] + reverse(all elements except last)

f([1, 2, 3, 4]) = [4] + f([1, 2, 3])
                = [4] + [3] + f([1, 2])
                = [4] + [3] + [2] + f([1])
                = [4] + [3] + [2] + [1]
                = [4, 3, 2, 1]

Since the intermediate values being passed between frames are integer arrays, the return type should be [Int]. Putting it all together:

func reverseArray(_ arr: [Int]) -> [Int] {
  // base case
  if arr.isEmpty { return [] }  
  
  let element = arr.last!
  
  // recursive step
  return [element] + reverseArray(Array(arr.dropLast()))
}

The child passing its value back to the parent happens here:

return [element] + reverseArray(Array(arr.dropLast()))

Try drawing the recursive tree for this yourself. You’ll see the child → parent value flow more clearly.

Now let’s explore parameters more directly. We’ll solve the same reverse problem, but with one constraint: reverse in-place. That means no copying — we can’t do [element] + reverseArray(...) anymore. We need to mutate the original array directly.

To do this in-place, we can use two pointers: a start index i and an end index j. We swap the elements at those positions, then move the pointers inward until they meet:

let i = 0, j = arr.count - 1
[1, 2, 3, 4, 5]
 |           |           
 i           j           
                         
swap i and j
[5, 2, 3, 4, 1]          
 |           |           
 i           j           
                        
i += 1, j -= 1          
[5, 2, 3, 4, 1]         
    |     |             
    i     j             

swap i and j                        
[5, 4, 3, 2, 1]         
    |     |             
    i     j

i += 1, j -= 1
[5, 4, 3, 2, 1]         
       |  
       |             
      i,j

The base case: stop when i >= j (the pointers have met or crossed in the middle).

So what do we pass as parameters? We need i and j — the current state of our two pointers. In other words: whatever the parent recursive frame needs to pass to the child recursive frame to keep the logic going correctly becomes a function parameter. If you prefer not to use parameters, you can maintain state in an outer variable instead — but we won’t cover that here.

The function doesn’t need to return anything since we’re mutating in-place:

func reverseInPlace(_ arr: inout [Int], startIndex i: Int, endIndex j: Int) {
  if i >= j { return }
  arr.swapAt(i, j)
  reverseInPlace(&arr, i + 1, j - 1)
}

Here’s the recursive tree for this:

f(arr = [1, 2, 3, 4, 5], i = 0, j = 4)
 |
f(arr = [5, 2, 3, 4, 1], i = 1, j = 3)
 |
f(arr = [5, 4, 3, 2, 1], i = 2, j = 2)
 |
Now, it is base case, so pop the stack.
Since the function returns void by default, there is nothing to merge.
Array is now mutated in place by means of pass-by-reference (inout param in Swift).
Even though it's called a tree, there's no branching here — it's a single linear chain of nodes.

Let’s put all four considerations together with one more problem: checking if a string is a palindrome. A palindrome reads the same forwards and backwards — "madam" is a palindrome, "hello" is not.

func isPalindrome(_ str: String) -> Bool {
  fatalError("Unimplemented")
}

Quick side note: if this came up in an interview, one good clarifying question is whether the check should be case-sensitive or case-insensitive.

This problem is similar to the in-place reverse. We keep a start index and an end index, and compare the characters at each position. If they match, we move inward. If they don’t match at any point, we know immediately it’s not a palindrome — no need to continue.

For example, "motor": 'm' vs 'r' — they don’t match, so we stop. It doesn’t matter that "oto" in the middle is symmetric.

Going through all four considerations:

Base case: stop when i >= j (pointers meet or cross) → return true; also stop if characters don’t match → return false
Subproblem: check characters at i and j, then move inward
Return type: Bool — we’re checking a true/false condition
Parameters: i and j — the current pointer positions

func isPalindrome(_ str: String) -> Bool {
  let chars = Array(str)
  return check(0, chars.count - 1)
}

// 4. Parameter i and j to get the parent recursive frame's state
private func check(_ i: Int, _ j: Int) -> Bool {
  // 1. Base case
  if i >= j { return true }
  if chars[i] != chars[j] { return false }
    
  // 2. Recursive logic and 3. return value
  return check(i + 1, j - 1)
}

First, the string is converted to a character array. Then a helper function check handles the recursion. That’s it! Try drawing the recursive tree for this one yourself.

Outro

This article covered everything you need to know to get started with recursion, laid out as clearly as possible. The key takeaway: visualization matters more than almost anything else. Once you can see recursion in your mind — through recursive stacks and trees — problems involving tree/graph traversal, backtracking, permutations, combinations, and dynamic programming start to feel far less intimidating.

The best way to get there is to look at lots of recursion problems and solutions, then challenge yourself: draw the recursive tree, ask yourself why a value is being returned, and ask why certain things are passed as parameters. Over time, this kind of thinking becomes second nature.

Next up: backtracking.

Until next time!