Tag: recursive

Tips on Writing Recursive Functions

Currently I am a newcomer to recursive functions.  When I started receiving prompts to write code that used recursion, my code didn’t work the way I wanted it to.

After practice, I have learned from my mistakes. I have still a ways to go, but I wanted to share the mistakes I was making and how to avoid them. Because if I made these mistakes, someone else might be making them too!

My Experience

First I’ll talk about my experience. Feel free to skip down to more general tips.

The first half of my problem was to pinpoint the concept I did not understand! After practice and office hours, I figured out that my lack of understanding was that I was not bringing up the value returned from the recursive call through the call stack.

Frantically trying to make my code work, I would throw in return statements in experimental places hoping to see a pattern. You can probably guess that didn’t work out.

I had a fuzzy understanding of what my code was doing. I didn’t fully understand everything in recursion, and since I didn’t, recursion was kind of like magic.

My course’s tech mentor recommend that I watch the call stacks in Chrome DevTools and/or draw the execution contexts out. I did both. I was not returning the right thing (if anything)!

By watching the call stacks in Chrome DevTools and drawing the execution contexts out, I saw my misunderstandings, and I concretely learned:

  1. Every time you recurse, you create a new execution context. If you start with a variable called counter equal to 0 in your recursive function, every time you recurse, the new execution context’s variable counter will be 0.
  2. Every time you recurse, if you have a return statement, your return statement will return something to the execution context above it.
  3. If you need something returned from the recursive function, when you call the recursive function, don’t just call it. Do something with what it returns. Do you need to save it to a variable? Do you need to add it to something? Push it to an array? Must it evaluate to true to do something else?

Just knowing that has clarified so many things!

Tips

Here are some other things to keep in mind. Some things you may know like the back of your hand, and others you may be great reminders.

Other Tips on Writing

  • Understand what your function needs to do
  • Make sample input
  • Make sample output for it (Is it an array, Boolean, object, etc.)
  • Looking at your sample output, find the common pattern. What are you getting? What changes between each input and output?
  • Figure out what the smallest or most basic output should be.
  • Write code that will get you this base case
    • (Note: There may be more than 1 base case)
  • Think of how you would get the other output (not the base case). This is probably where the recursive call comes in.
  • In your recursive call, pass in the correct amount of arguments
  • If you are returning something from your recursive call, make sure to save it a variable, so that it can be returned up through the call stacks

Tips on Debugging/Understanding Your Recursive Function

  • If you have a for loop, follow your code and write the output of what your recursive loop should be
    • Write the output of what your 1st recursive loop should be
    • Write the output of what your 2nd recursive loop should be
    • Write the output of what your 3rd recursive loop should be
    • … And so on
  • Draw out the execution context
  • Console.log is your friend
  • Use Chrome DevTools and watch the call stack
    • You can compare it to what you wrote your expected output to be

For other newcomers like me, do you have any questions on writing recursive functions? For experienced programmers, what tips would you share from when you learned recursion?

(This post may be edited over time)

Advertisements