Recursion

basic idea is taking one problem and doing it over and over on a smaller piece or on a chaning piece

until you hit some endpoint which we call the base case.

 

Recursion is different way of thinking about writing solution.

can choose a solution iterative way or recursive way.

 

A process that calls itself.

 

ex) JSON.parse / JSON.stringify

      document.getElementById

      Object traversal

---

 

the call stack

- it is a stack data structure

- anytime a function is invoked it is placed (pushed) on the top of the call stack

- when Javascript sees the return keyword or when the function ends, the compiler will remove(pop)

 

How recusive function works

 

when we write recusive functions, we keep pushing new functions onto the call stack.

 

• Base Case - a situation when the recursion ends
• Different Input

function sumRange(num) {
  if(num === 1) return 1;
  return num + sumRange(num-1);
}

spot the base case?

notice the different input?

what happens if we didn't return?

 

the pitfalls the common problems that arise 

- no base case

- forget return, wrong return.

 

---

Helper Method Recursion

 

common design pattern when we are trying to compile some sort of result usually an array or some other data structue.

just means defining a function arount it.

an outer function that's not recursive which calls an inner function which is recursive

 

function outer(input) {
  var outerScopedVariable = {};
  
  function helper(helperInput) {
    // modify the outerScopedVariable
    helper(helperInput--);
  }
  
  helper(input)
  
  return outerScopedVariable;
}

---

Pure Recursion

the function itself totally self-contained in its recursive.

 

function collectOddValues(arr) {
  let newArr = [];
  
  if(arr.length === 0) return newArr;
  
  if(arr[0]%2 !== 0) newArr.puth(arr[0]);
  
  newArr = newArr.concat(collectOddValues(arr.slice[0]));
  return newArr;
}

 

• for arrays, use methods like slice, the spread operator and concat 
  that make copies of arrays so not to mutate them
• Strings are immutable. so will need to use methods like slice, substr, substring to make copies of strings
• Object.assign, spread operator to make copies of objects

---

Recursive Problem Set

 

1. power

//Write a function called power which accepts a base and an exponent.
//This function should mimic the functionality of Math.pow()
// power(2,0) // 1
// power(2,2) // 4
// power(2,4) // 16

function power(base, exponent){
    if(exponent === 0) return 1;
    return base* power(base,exponent-1);
}

 

2. factorial

// Write a function which accepts number and returns the factorial of that number.
// factorial(1) // 1
// factorial(2) // 2
// factorial(4) // 24
// factorial(7) // 5040

function factorial(num){
   if(num===0) return 1;
   return num*(factorial(num-1));
}

 

3. productOfArray

// Write a function called productOf Array which takes in an array of numbers 
// and returns the product of them all.
// productOfArray([1,2,3]) // 6
// productOfArray([1,2,3,10]) // 60

function productOfArray(arr) {
    if(arr.length === 0) return 1;
    return arr[0]*productOfArray(arr.slice(1));
}

 

4. resursive Range

// recursiveRange(6) // 21
// recursiveRange(10) // 55 

function recursiveRange(input){
   if(input === 0) return 0;
   return input+recursiveRange(input-1);
}

 

5. fib

// Write a recursive function calld fib which accepts a number
// and returns the nth number in Fibonacci sequence.
// fib(4) // 3
// fib(10) // 55
// fib(28) // 317811
// fib(35) // 9227465

function fib(num){
  if(num <= 2) return 1;
  return fib(num-1) + fib(num-2);
}