Improve Concept Exercise: recursion

[SleeplessByte]

Getting started

Here you can read about what Concept Exercises are and how they are structured:

• What are Concept Exercises?
• Concept Exercises
• Concepts

If you have not done so yet, it is probably also helpful to do a couple of "Learning Exercises" (this is how they are called on the site) yourself. You can also look at the code of an existing concept exercise like bird-watcher (concept for-loops) for reference.

See the documentation above (general documentation), as well as How to implement a Concept Exercise in JavaScript.

Goal

This PR has been merged optimistically. The improvement goal is to implement:

• .docs/about.md
• .docs/hints.md
• .docs/instructions.md
• .docs/introduction.md
• languages/javascript/exercises/concept/README.md (check if updated)

Your mission, should you accept it, is to apply the story from the fork-original, or come up with a new one, write the step-by-step instructions, provide at least 1 hint per instruction (see other exercises for the format) and to provide some interesting facts about recursion or the ways to recurse in the about.md document. Optionally talk about tail-call optimisation/tail-recursion and the lack thereof in JavaScript.

⚠ The next message is of vital importance and must be resolved using language in instructions.md and usage of hints.md.

This exercise was simplified from the fork-original. This allows for an implementation with recursion in the second fuction orderPrice. However, the test cases are structured in such a way so that the recursion solution will yield an error. These errors are more common than you think and this exercise introduces students to them. It is vital to name both errors in the instructions.md and refer to hints.md if a student needs help resolving them.

export function orderPrice([order, ...others]) {
  if (!order) {
    return 0
  }

  return pizzaPrice(order.pizza, ...order.extras) + orderPrice(others)
}

This code looks perfectly fine, and it "is". Another variant is to destructure as the first line of the program. This code will yield a Memory Allocation Error (OutOfMemory), because each call to the function, the input array gets duplicated (into ...others). That means that if 10.000 items are put into this function, that the first call it will reference a 9.999 item array, and in the second call it references a 9.998 item array...

export function orderPrice(pizzaOrders) {
  if (pizzaOrders.length === 0) {
    return 0
  }

  const order = pizzaOrders.shift()
  return pizzaPrice(order.pizza, ...order.extras) + orderPrice(pizzaOrders)
}

So the example above fixes this issue. It mutates the input array, and therefore only every 10k items are stored in memory (yay). This solved the memory error, but yield a Maximum call stack size exceeded. This is intended. The default stack size in node can be found by running a cli command (something to perhaps mention in after.md):

When running node --v8-options, somewhere in the huuuuge list of options, you'll find:

--stack-size (default size of stack region v8 is allowed to use (in kBytes))
        type: int  default: 984

That number can be used to calculate the stack size. In short: There is not enough for the test. It must be solved using some imperative loop (for loop, .foreach, or best: .reduce)

Help

You can choose to do this solo-style, or collaborate with multiple people on this. My suggestion would be is to

1. first accept this issue by saying "I'd like to work on this" (you will not get a response from me. Just go with it) and optionally request that someone works with you (and wait for a second person to accept your request).
2. Use this issue to write down what you need (collect reference material) and discuss, if necessary, what to write and what not to write. Here is a list to start with:
   • recursion generic concept reference
   • Tail call optimisation in JavaScript
3. Create a PR and set "exercism/javascript" as reviewers. Additionally you can write in #maintaining-javascript that your PR is ready for review. Once you incorporated any critical feedback that the reviewer might give you and the PR is approved, it will be merged by a maintainer.

Credit

This contribution grants you an author slot. Add your username to the authors key in the config file.