Simple Recursion & Challenges(ruby, js, python)

What is Recursion?

Recursion is where a function calls itself from within the function.

Example: String Reversal

function reverseString(string){
    return (string === '') ? '' : reverseString(string.substr(1)) + string.charAt(0);
} 

How is it able to call itself from within the function and keep the return values? It stores each call into the Call Stack.

Call Stack

The Call Stack is a Stack Data Structure that stores an ordered series of items just like a list. When you think of an array, you can add and remove an item at any index. With a stack, the first item added is the last item to be removed.

When you go past the maximum call stack size, it is called Stack Overflow. If you don't include a condition in a method in order to stop a recursive call, it will loop on endlessly, adding on more calls to the call stack, until memory runs out.

This is a problem with Recursion. The computer needs to allocate memory for things. You can run out of memory when the call stack size is exceeded. In order to stop this from happening, you need to include a base case.

The Base Case

There are two things you have to do in a recursive function. You have to have a recursive call and a base case.

The base case is a condition set in the function determining when the recursive call should stop.

There is one problem when it comes to returning values. Remember that the first item added to a stack is the last item removed from the stack. Once the base case condition is met, the stack will remove items, starting with the last item added to the call stack.

So let's say we don't explicitly return a value we want to receive in JavaScript. It will get to the last recursive call, return the value, then will start popping off the rest of the calls within the call stack. The value you wanted to get will not be there, once you get to the final return.

You would have to explicitly return the recursive call in order to get the correct value. The return value of all recursive calls would be the final recursive call return value.

Duplicate Letter Challenge

If you are up to it, here are some recursion challenges. The JavaScript Solution details the process I took in solving the challenge, as well as a way to solve it without Recursion.

Guidelines:

1. You must use Recursion.
2. You must take in a string as an argument to the function.
3. The return value must be a Hash(Ruby)/Object(JS)/Dictionary(Python), containing keys of each letter in the string.
4. The value to each key will be how many times the key appears in the string.

• JavaScript Solution
• Ruby Solution
• Python Solution