recursion

What is recursion

Recursion is the fuction that calls itself. This is good tool to solve the big problem with divide and conquer approach.

Rules

1. Exit condition : stack overflow can occurs if there is no exit condition
2. Divide-and-conquer approach

Pibonacci

Basic

divide and conquer with $O(n^2)$ time complexity

function getNthFibo(n) {
  if (n <= 1) {
    return n
  } else {
    return getNthFibo(n - 1) + getNthFibo(n - 2);
  } 
}
console.log(getNthFibo(3))

tail recursion

time complexity : $O(n)$
space complexity : $O(n)$

function getNthFiboBetter(n, lastlast, last) {
  if (n == 0) {
    return lastlast;
  }
  if (n == 1) {
    return last;
  }
  return getNthFiboBetter(n-1, last, lastlast + last)
}

Pascal's triangle

Pascal's triangle is consisted of values that is sum of two values located above.