re: What makes recursion hard VIEW POST

re: 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...

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).

this could be its own blog post. Thank you!

code of conduct - report abuse