Discussion on: What makes recursion hard

Recursion is a strange concept at first for sure. Something that helped me really understand it was the idea that recursion is all about context.

so the function basically calls it self but changes its context (via the updated parameters) until it reaches a "base case" or a case where you finally return a primitive and don't call the function again.

since Fibonacci is recursively defined as f(n) = f(n-1) + f(n-2) it lends itself to a recursive solution in programming.

in javascript we setup the function as

function f(n) {
  if (n === 0)
    return 0;
  if (n === 1)
    return 1;
  return f(n-1) + f(n-2);
}

but you can see that all we are doing is on each function call we are checking if the parameter is 0 or 1 and returning 0 or 1 respectively if they infact are. Otherwise we call the function again, but with a new parameter n-1 and n-2.

you can visualize this as:

// f(5)
return f(4) + f(3);
// which translates to =>
return f(3) + f(2) + f(2) + f(1)
// to =>
return f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + 1
// to =>
return f(1) + f(0) + 1 + 1 + 0 + 1 + 0 + 1
// to =>
return 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
// to => 
return 5
// => 5

hope this helps :D