Sep 1, 2018 · 2 min read
There’s two different ways you could think of it.
Option 1: The basic solution
- If we’re trying to calculate recFunc(n), then recFunc(n-1) is 1 step simpler.
- We assume that recFunc(n-1) will work correctly.
- 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
- 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.
- Assume that recFunc(n-2) works correctly.
- 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!
