Daniel King
Sep 1, 2018 · 2 min read

There’s two different ways you could think of it.

Option 1: The basic solution

  1. If we’re trying to calculate recFunc(n), then recFunc(n-1) is 1 step simpler.
  2. We assume that recFunc(n-1) will work correctly.
  3. Note that, to build up from recFunc(n-1) to recFunc(n), the process is different depending on whether n is odd or even. It would look like this (I left part of the function blank, try filling it in):
function recFunc(n) {
// Base case
if (n === 1) {
return [1]
}
// Recursive case
if (n % 2 === 1) {
// TODO
} else {
// TODO
}
}

Option 2: The clever solution

  1. If we look closely at the examples, we might notice that recFunc(9) (543212345) is the same as recFunc(7) (4321234), except with 5’s attached to eiter end. Similarly, recFunc(6) (321123) is the same as recFunc(4) (2112), except with 3’s attached to either end. I conclude that recFunc(n-2) is closely related to recFunc(n) in all cases, and therefore it might be a better candidate to use as the “one step simpler” problem.
  2. Assume that recFunc(n-2) works correctly.
  3. We think about how we can construct recFunc(n) from recFunc(n-2). Note that we actually need to include recFunc(2) as a base case as well, since there’s no recFunc(0) (I left part of the function blank again):
function recFunc(n) {
// Base cases
if (n === 1) {
return [1]
} else if (n === 2) {
return [1, 1]
}
// Recursive case
const nextNumber = // TODO
return [nextNumber, ...recFunc(n - 2), nextNumber]

This solution is more computationally efficient, because the function only needs to go through half as many recursive evaluations. On the other hand, it required us to think outside the box a little bit to determine what the “one step simpler” problem was.

Cheers!

Daniel King

Professional Software Engineer and Educator, amateur Musician, armchair Personal Finance Expert

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade