Recursion 1. Introduction 2. Anatomy of Recursion 3. Factorial 4. Fibonacci 5. Recursive vs. Iterative 6. When to Use Recursion 7. Reverse the String with Recursion
1. Introduction• Algorithms allow us to use a language built-in data structures to perform actions on that data.• Data Structures + Algorithms = Programs• Class{} + Function() = Programs • Certain algorithms allow us to simplify our Big-O complexity into smaller or better time complexity.• Recursion isn't technically an algorithm. It's more of a concept.• Recursion is when you define something in terms of itself. It's a function that refers to itself inside the function.• •
function inception() { inception()}
 • Recursion is really good for tasks that have repeated subtasks. (e.g. traverse() in our tree implementation in previous sections)• Recursion is used extensively in searching and sorting algorithms.• Recursion can lead to stack overflow. (sample code above causes stack overflow). 2. Anatomy of Recursion• Every recursive function needs to have something called a base case or a stop point.• Recursive functions have two paths:– Recursive function (that is being called again)– Base case• Here's how to add a base case to the code above and avoid stack overflow,
let counter = 0;function inception() { if (counter > 3) { return 'done'; } counter++; inception();}
 • Note: If we run the code above, it won't return done, instead it'll return undefined! The reason is recursion is a function of functions (inception(inception(inception(inception('done')))). So, when we return from the most inner function (returning done), it has to get bubbled up to the most outer function. Here's how to fix the code above,
let counter = 0;function inception() { if (counter > 3) { return 'done'; } counter++; return inception();}
 3. Factorial• Write two functions that finds the factorial of any number. One should use recursive and the other should just use for loop.
function findFactorialIterative(number) { let answer = 1; // you actually no longer need the if statement because of the for loop // if (number === 2) { // answer = 2; // } for (let i = 2; i <= number; i++) { answer = answer * i; } return answer;} function findFactorialRecursive(number) { if(number === 2) { return 2; } return number * findFactorialRecursive(number - 1)} findFactorialIterative(5);findFactorialRecursive(5); //If you want, try to add a base case condition for the recursive solution if the parameter given is less than 2
 4. Fibonacci• Given a number N, return the index value of the Fibonacci sequence.• In Fibonacci sequence each value is the sum of two previous values.
// Given a number N return the index value of the Fibonacci sequence, where the sequence is: // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...// the pattern of the sequence is that each value is the sum of the 2 previous values, that means that for N=5 → 2+3 //For example: fibonacciRecursive(6) should return 8 function fibonacciIterative(n){ let arr = [0, 1]; for (let i = 2; i < n + 1; i++){ arr.push(arr[i - 2] + arr[i -1]); } return arr[n];}fibonacciIterative(3); function fibonacciRecursive(n) { if (n < 2){ return n; } return fibonacciRecursive(n - 1) + fibonacciRecursive (n - 2)} fibonacciRecursive(6)
 5. Recursive vs. Iterative• Anything you do with a recursion CAN be done iteratively (loop). Why would we want to use recursion then?• Recursion sometimes make the code more readable.• Recursion is DRY (Don't Repeat Yourself).• The downside of recursion is creating extra memory footprint (large stacks), because every time we add a function to the call stack, it adds extra piece of memory.• As a useful rule, we should use recursion when you're working with data structures that you're not really sure how deep they are (so you don't know how many loops you need to have).– Recursion is very useful in traversals (tree data structures) because that is often the case.• Tail Call Optimization: A functionality in some languages (e.g. JS ES6) that allows recursion to be called without increasing the call stack. (Tail Call Optimization) 6. When to Use Recursion• When it gets to complicated problems like traversing or searching through trees or graphs, recursive is better than iterative.• With sorting (Merge Sort, Quick Sort), there are cases that recursion is preferred.• Use the following rules for when to use recursion:– Every time you are using a tree or converting something into a tree, consider recursion.* Divide into a number of subproblems that are smaller instances of the same problem.* Each instance of the subproblem is identical in nature.* The solutions of each subproblem can be combined to solve the problem at hand.– Divide and conquer using recursion. (e.g. looking through a phonebook) 7. Reverse the String with Recursion• Here's a code to reverse a string using recursion,
function reverseString(str) { let arrayStr = str.split(""); let reversedArray = []; //We are using closure here so that we don't add the above variables to the global scope. function addToArray(array) { if(array.length > 0) { reversedArray.push(array.pop()); addToArray(array); } return; } addToArray(arrayStr); return reversedArray.join("");} reverseString('yoyo master'); function reverseStringRecursive (str) { if (str === "") { return ""; } else { return reverseStringRecursive(str.substr(1)) + str.charAt(0); }} reverseStringRecursive('yoyo master');