Unit 2 - Divide & Conquer
2.
2 - Recursion (part 2)

Reminder: Recursion

  • the idea that something will re-occur in smaller amounts

    • divides a complex problem into smaller sub-problems (i.e. divide and conquer)

    • subproblems are smaller instances of the same type of problem.

  • is somehow self-referential (calls itself)

Converting Strings to Integers

The parseInt() and Number() functions are invaluable. We couldn't do a lot of the work we do without them. But how do they work? Let's focus on parseInt().

    • Take a string and (for now) assume it is made of only the digits 0-9. For example "4293"
      Hints:
      -
      The length of that string (currently 4) can be a very helpful piece of information.
      - The integer ascii character values for characters '0' to '9' are 48 to 57.
      -
      JavaScript has a charCodeAt() function that gives you the integer code value of a character.

    • Can we recursively convert a String to a number? Let's generate some pseudocode to do it.

Factorials

In mathematics, a factorial is defined as: n! = n x (n-1) x (n-2) x (n-3) x ... x 3 x 2 x 1
For example,
5! = 5 x 4 x 3 x 2 x 1 = 120

  • What is the base case?

  • Important notes:

    • n is always a non-negative integer.

    • By definition, 0! = 1

  • What is 1! ?

Head over to Replit (find task 2.2a). Take a moment and devise a recursive algorithm that will return the factorial of a number:
function factorial(n) {...}
If you need some assistance with that, take a look at the
notes for 2.1 - Recursion (part 1)