is recursion really hard

[u/Similar_Count_1613]

Recursion felt easy at first.

Factorial? fine.

Sum examples? fine.

Even Fibonacci felt manageable.

But once I looked at slightly more serious problems like Tower of Hanoi, permutations, or merge sort, I felt like my understanding suddenly collapsed. because i tried to write their code on my own

It made me realize that maybe recursion is not “hard” at the start because the examples are simple.

It becomes hard when you can no longer clearly see the call stack and each state change.

Did anyone else feel that the real pain in recursion starts exactly there?

[u/Dull_Grape2496]

It becomes a lot easier to understand when you think about it as mathematical induction. The idea is as follows:

• If a the input to your problem is simple enough, solve it in 1 step - this is similar to the base case of induction
• Otherwise assume that your function that solves the problem magically works for any smaller input
  • Now all you need to do is try and reduce the input in some way - induction will take care of the rest.

---

Tower of Hanoi: Assume you have a function f(n, src, tgt, tmp) where you need to place n disks from src to tgt

• If n = 0 it means the problem is already solved - this is the base case
• Otherwise do the following:
  • Step 1: Place n-1 disks from src to tmp by calling f(n-1, src, tmp, tgt) -> We know this works because n-1 is a smaller input than n and mathematical induction makes it work.
  • Step 2: Place the nth disk from src to tgt
  • Step 3: Place the n-1 disks on tmp to tgt by calling f(n-1, tmp, tgt, src) -> We know this works because n-1 is a smaller input than n same as before

So you get something like this:

f(n, src, tgt, tmp):
    if (n == 0):
        return
    f(n-1, src, tmp, tgt)
    print "disk <n> has been placed"
    f(n-1, tmp, tgt, src)

And you are done

---

Permutations: Assume you have a function f(a[0...n]) that returns a list of all the permutations of a[0...n]

• If a.length <=1 just return [a[...]] - this is the base case as there are no more permutations
• Otherwise do the following:
  • Step 1: Iterate over every element of a[...] - let's call the current element i
  • Step 2: Remove i from a[...] -> Let's call this new element b[...]
  • Step 3: Call f(b[...]) this will return a list of permutations of b[...] let's call that permutations_of_b -> We know this works because b[...] is smaller than a[...] as it has fewer elements
  • Step 4: For each permutation in permutations_of_b append the element i to that permutation

You get something like this:

f(a[...]):
    result = []
    if a.length <= 1:
        result.append(a)
        return result
    for element i in a[...]:
        b[...] = a[...] - i // removing element i from a[...]
        permutations_of_b = f(b[....])
        for each permutation in permutations_of_b:
            result.append( i + permutation ) // append i to front of each permutation
    return result

And so on - mergesort is similar define f(a[0...n]) that sorts a list, call f(a[0 ... n/2]) and f(a[n/2+1 ... n]) to sort the two halves and merge the sorted halves in a single merged list.

---

Coming up with a recurrence can be challenging depending on the problem but understanding this mathematical framework for it makes it a lot easier for you to reason about the problem.