Discussion on: What makes recursion hard

[Austin S. Hemmelgarn]

I don't know where to start

A tip on this one in particular. When you need to come up with a recursive function, always start from your exit cases (that is, the cases where the function won't call itself again), and work your way up from there. This helps put the focus more on the implementation than the original algorithm, which in turn helps keep things sanely organized.

There's nothing more nerve wracking than writing what should be a valid solution only to get Range Error: Maximum call stack size exceeded

Note that this is not an issue in all languages. Elixir and Erlang for example will never exhaust the call stack as long as you write your recursive function correctly (that is, as long as the last code executed by the function is a call to another function or itself), and many other heavily functional programming languages behave similarly. The general technique for avoiding such things is known as 'tail-call optimization' (TCO for short). In short, it simply avoids the call stack if the last thing for a function to do is to call another function.

ES6, notably, technically requires automatic TCO as part of the implementation, but almost nobody actually implements it (notably, it's the only mandatory part of ES6 that isn't implemented in either SpiderMonkey (Firefox) or V8 (Chrome and node).

[Jasterix]

Thanks, the first part of your commend is pretty helpful. How do you recommend debugging a recursive function? In my case, I couldn't reach my exit case once I implemented the recursion

I don't quite know enough to understand the second part of your comment, but am sure it will make sense once I go deeper into algorithms  :)

[Austin S. Hemmelgarn]

Thanks, the first part of your commend is pretty helpful. How do you recommend debugging a recursive function? In my case, I couldn't reach my exit case once I implemented the recursion

Two big things come to mind:

Put an upper limit on the recursion so it won't loop forever.

At least when debugging, this gives you an easy way to be sure that the function is just looping in cases where it should only get called a couple of times.

In JS, this would look something like the following for a Fibonacci sequence:

function fibonacci(index, depth) {
    if (depth >= 20) throw new Error("Exceeded max call depth")

    if (index === 1 || index === 2) {
        return 1
    } else {
        return fibonacci(index - 1, depth + 1) + fibonacci(index - 2, depth + 1)
    }
}

In essence, you're explicitly enforcing a much lower limit on the call stack size than the language natively does, so you'll see much sooner if your code is stuck looping infinitely. Of course, this requires you to have some reasonable understanding of how deep the stack might go for your test cases (the above function will just fail to find any term in the Fibonacci sequence past the 19th, because anything further requires a call depth of at least 20), but for many cases this is not hard to figure out, and you can always bump up the limit if you need to.

Some language runtimes will also let you control the max call stack depth directly, which is the preferred approach to take for this if your language of choice supports it because it doesn't require you to modify your code at all.

Actively inspect the state of the conditions you use to determine your exit case.

In short, step through a call of the function in a debugger, and pay attention to how the conditions for recursion evaluate each time. This can be a bit tedious, but it really is the best way to figure out why you're not terminating if you get stuck in an infinite loop.

---

Also, couple of more general tips for actually implementing recursive functions:

• Return results directly instead of storing them in a temporary variable and returning that. IOW, instead of ret = foo(bar); return ret; do return foo(bar). This helps make the control flow much more explicit, which makes it much easier to ensure that you're not accidentally evaluating multiple conditionals to true when deciding to recurse or not. It also allows languages that support the optimization I mentioned in the second part of my previous comment to actually use it.
• Put your exit cases first in the conditionals, and your recursion cases last. This makes it a bit easier to understand the structure, especially in situations where you recurse in the general case (like the Fibonacci sequence).
• Prefer if/else blocks to case statements. It's a lot easier to clearly track what's going on with an if/else block for most people, and it also completely sidesteps one of the coding mistakes that can cause infinite recursion (forgetting to correctly break out of a case statement after the first match).

[Jasterix]

this could be its own blog post. Thank you!