What makes recursion hard

I had my first technical interview this week. My only whiteboard question: complete my least favorite challenge, the dreaded recursion.

Prompt:

Create a function that accepts a number and returns the sum of of the Fibonacci numbers up to that number

Results:

Unsurprisingly, I wasn't able to pull off the recursion. In the stress of the moment fixated on that instead of solutions that don't use recursion. But since then I've been wondering why recursion is so difficult for me. This is what I cam up with:

1. I don't know where to start
   1. Although I understand recursion theoretically, implementing it is a different case altogether
2. My function never returned my base case
   1. Why? No idea
3. Especially when it's a problem I've seen before, I fixate too much on recreating solutions I've seen
   1. In this scenario, familiarity worked to my disadvantage. Instead of going line by line, I got frustrated by what I thought the solution should look like
4. Nerves and stress
   1. There's nothing more nerve wracking than writing what should be a valid solution only to get Range Error: Maximum call stack size exceeded
5. Lack of experience
   1. As frustrating as failing can be, I do realize that these things- interviewing, solving unfamiliar challenges, even recursion- will get easier with more practice

Conclusion:

Three days after the interview, I'm still frustrated by my perceived lack of progress. But I also feel even more motivated to understand JavaScript concepts better. Instead of recreating code I've memorized, my goal is to

1. Understand JavaScript is doing under the hood
2. Be able to break complex problems into smaller ones
3. Write code that does what I intend for it to

I also want to consume resources like this CSX video that focus on exploring programming paradigms

For now, though, I think it's okay to be a little disappointed in myself

Comments

[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!

[Cubicle Buddha]

I don't really know why recursion is so hard
--> I don't really know why recursion is so hard
-----> I don't really know why recursion is so hard
--------> I don't really know why recursion is so hard
-----------> I don't really know why recursion is so hard
--------------> {explosion}

All jokes aside, recursion is hard to debug and rarely has a good use case in typical production applications. So I'm very sorry to hear that you had a bad interview experience. It sounds like you might have dodged a bullet. What I mean is that I don't know if I'd want to work for a company that requires a solution to use recursion (or any specific solution for that matter).

[Jarod Smith]

Recursion is a strange concept at first for sure. Something that helped me really understand it was the idea that recursion is all about context.

so the function basically calls it self but changes its context (via the updated parameters) until it reaches a "base case" or a case where you finally return a primitive and don't call the function again.

since Fibonacci is recursively defined as f(n) = f(n-1) + f(n-2) it lends itself to a recursive solution in programming.

in javascript we setup the function as

function f(n) {
  if (n === 0)
    return 0;
  if (n === 1)
    return 1;
  return f(n-1) + f(n-2);
}

but you can see that all we are doing is on each function call we are checking if the parameter is 0 or 1 and returning 0 or 1 respectively if they infact are. Otherwise we call the function again, but with a new parameter n-1 and n-2.

you can visualize this as:

// f(5)
return f(4) + f(3);
// which translates to =>
return f(3) + f(2) + f(2) + f(1)
// to =>
return f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + 1
// to =>
return f(1) + f(0) + 1 + 1 + 0 + 1 + 0 + 1
// to =>
return 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
// to => 
return 5
// => 5

hope this helps :D

[Zohar Peled]

There's only one way to learn how to write code: Write code.
Don't get me wrong, you still need to read, a lot.

In my experience, the best way to understand what some unfamiliar code does is to copy & paste it into your test environment and run it through a step-by-step debugger, checking out the variables values at every row.

Note that this (and recursion also) doesn't apply only to javascript, but to any programming language.

[Fernando Crozetta]

Oh, the pressure on us, right?
Reading this made me remember a challenge I participated in some conference months ago. Same problem.
for recursive functions, what I usually do is start creating the exit condition, and then working on what has to be done in the function.
When I had to implement with a lot of other developers watching me code, I kinda panicked, almost couldn't finish it.
It was my first time doing a challenge like that, and it was kinda scary.

[Rachel Soderberg]

My first technical interview, I was asked to explain how to get a factor. I kept thinking factorials because I had been studying them so much. Ended up making a fool out of myself and got incredibly flustered. Needless to say I did not get the job heh.

[Jasterix]

oh man I relate to that so hard lol sorry to hear about the job though

[Rachel Soderberg]

Honestly, it was just an internship and some of the other questions were of a strange difficulty level for where an intern should be. I probably dodged a bullet as well. :)

[Emmanuel Okiche]

You could add a debugger at the top inside your function and run it in chrome to see how the functions are added and popped from the stack.
Also, track the return value at each stage.

Remember, start small.
Start learning about recursion with the most basic example(maybe factorials).

Finally, patience, research and practice.

All the best

[Jasterix]

great idea!

[thekhairul]

I think most tutorials miss one fundamental part of recursion which is call stack. It's important to understand how call stack works, how it pauses its execution context while calling an inner function and then resumes from there with a possible return value from that inner function. "Recursion is a function calling itself" sounds simple but very much incomplete without clear concept of call stack and how functions work in a language. One youtube channel I admire the most when it comes to understanding basic DS/Algo is mycodeschool . It has a dedicated playlist of recursion

[Theofanis Despoudis]

Practice 2 to 5 problems from Leetcode or Hackerearth each day and in 1 month you will be a ninja

[Jasterix]

I started doing some basic problems on CSX after the interview