Review of Week 3 Day 4 Learning Objectives

1. Given a recursive function, identify what is the base case and the recursive case.

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

In this case, the body of our if block, when arr.length === 1 is our base case.

2. Explain when a recursive solution is appropriate to solving a problem over an iterative solution.

There are no hard and fast rules as to when recursive solutions are appropriate compared to an iterative solution. Your comfort with each type of programming will inform which paradigm you prefer. List comprehension functions, like reduce, map and filter are implemented very cleanly with recusion, and indeed were introduced by functional languages before being adopted by a whole host of predominantly iterative languages including JavaScript.

Through problems, like our naive recursive solution to Fibonacci, we learn that there are definitely times when we a problem can be expressed cleanly as a recursive algorithm, but will have very poor performance. We clearly need to consider more than just lines of code and clarity of expression when deciding whether or not to use a recursive solution.

There are certain classes of problems: i.e. problems that traverse nested arrays, objects, graphs or trees (that is, data with recursive structure) which lend themselves especially well to recursive solutions.

As we continue to gain experience with algorithms in this course, we will learn about the complex topic of runtime complexity - the analysis of the performance of our code. At that time, we will have an understanding of the principals of code performance, which will enable us to discuss the merits of various algorithms, both iterative and recursive, in a more concrete fashion."

3. Write a recursive function that takes in a number, n, argument and calculates the n-th number of the Fibonacci sequence.

function fibonacci(n) {
    if (n <= 2) {
        return 1
    }
    return fibonacci(n - 1) + fibonacci(n-2);
}

4. Write a function that calculates a factorial recursively.

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

5. Write a function that calculates an exponent (positive and negative) recursively.

function exponent(num, power) {
    if (power === 1) {
        return num;
    }
    if (power > 1) {
        return num * exponent(num, power-1);
    }
    if (power === -1) {
        return 1 / num;
    }
    if (power < 1) {
        return (1/num) * exponent(num, power+1);
    }
}

6. Write a function that sums all elements of an array recursively.

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

7. Write a function that flattens an arbitrarily nested array into one dimension.

function flatten(arr) {
    let res = [];
    arr.forEach(el => {
        if (Array.isArray(el)) {
            let flattened = flatten(el);
            res = res.concat(flattened); 
        } else {
            res.push(el);
        }
    });
    return res;
}

8. Given a buggy recursive function that causes a RangeError: Maximum call stack and examples of correct behavior, debug the function.

When we have a recursive solution that overflows the call stack, we know that the problem must be in our base case or our recursive step. Our algorithm will not make progress if our recursive step is missing, and our algorithm will not know when it has completed without a base case.