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)