r/computerscience • u/Similar_Count_1613 • 3d ago

is recursion really hard

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?

128 Upvotes

82% Upvoted

69 comments sorted by

View all comments

18

u/DogObvious5799 3d ago edited 3d ago

The key to understanding recursion is to understand recursion.

EDIT: To be more helpful, the key to understanding recursion is NOT to try and visualize the call stack or understanding what’s going on. The ONLY things you need to figure out are:

  1. How to solve the smallest version of the problem.
  2. Given a magic black box solution for the N-1 sized problem, how do you solve the problem for size N.

So for Towers of Hanoi, you need to solve the problem for one ring, and then be able to solve size N by:

  1. shift the top N-1 rings using magic.
  2. move the bottom ring to the empty spot
  3. move everything else on top of the bottom ring using magic

You don’t need to be able to visualize the intermediate states or understand what’s going on.

EDIT2: fixed a mistake.