Recursion with Numbers/Strings

Number Recursion

When recurring with numbers, there isn't one go-to number to use as a base case; it depends on what we want to do with our numbers.

If we're adding or subtracting, a good base case to start with might be adding or subtracting zero to our number, since this won't change its value! On the other hand, if we were doing something a little more complicated like multiplication, we might start with a base case where we just multiply or divide by one, since this won't change the number we're starting with either. As with writing other recursive functions, starting with the simplest case is the way to go!

Example: Addition Function

If we want to use recursion with addition, we know our function would take in a number, n, and how much we want to add to it, m. Calling this function might look like add(n, m).

The simplest thing we can do is add zero, since that doesn't change my original value. Knowing this, if the value we would add (the m value) is zero, then all we want to get back is the original number, n.

The next simplest thing we could do would be to add one. Since we already figured out that adding zero doesn't change anything, we could say that adding one is the same as adding one to the result of adding zero.

We can use this logic to figure out how to add two. 2 is the same as 1 + 1, so adding two is the same as adding one to the result of adding one to our number. If we keep thinking through these steps for more complicated cases, we'll get a pretty good idea of what our recursive function is going to look like.

Here's how we'd put all this together:

let add = (n: number, m: number): number => {
    if (m === 0) {
        return n;
    } else {
        return 1 + add(n, m - 1);
    }
};

In the above example we take some number, n, and we add 1 m number of times. We decrement m in our recursive step so that we will eventually reach our base case m === 0.

In general, it helps with recursion to start with the base case then think about more complicated cases in terms of this base case.

Example: Subtraction Function

Writing a recursive function for subtraction won't be too different from the one we just wrote for addition, but instead of adding one each time we'll subtract one each time!

let sub = (n: number, m: number): number => {
    if (m === 0) {
        return n;
    } else {
        return sub(n, m - 1) - 1;
    }
};

Here we start with some number, n, and we want to subtract 1 m number of times from it. In the recursive step we subtract one from the recursive call to update our final value, as well as subtracting 1 from m so that we will eventually reach our base case of m === 0.

Recursion with Strings

Recursion is not exclusive to numbers! We can use similar techniques to recurse through strings. Often, bases cases will search for an empty string, or the presence of a particular character.

In the below example, we are going to write a recursive function that concatenates various strings depending on the presence of specific characters:

if the input string has the character "1," the output string should include "eE"
if the input string has the character "0," the output string should include "oO"
if the input string has a character other than those above, the output string should include "-"
these transformations should occur in the same order as the input string as illustrated below
- 101 ->eEoOeE
- 0031 -> oOoO-eE

let stringRecursion = (input: string): string => {
    if (input === "") { // => base case!
        return "";
    } else if (input[0] === "1") { // => recursive call accounting for "1"
        return "eE" + stringRecursion(cutOffFrontChar(input));
    } else if (input[0] === "0") { // => recursive call accounting for "0"
        return "oO" + stringRecursion(cutOffFrontChar(input));
    } else { // => recursive call accounting for any character other than "0" or "1"
        return "-" + stringRecursion(cutOffFrontChar(input));
    }
};

// the below function is a "helper" function that returns the input string with the front character removed
// usually with numbers we can use mathematical operators to get closer to the base case
// with Nodes/Linked Lists, we use rest(_), which has a similar effect of removing the front Node of the list
let cutOffFrontChar = (inputString: string): string => {
    let outputString = "";
    if (inputString.length === 0 || inputString.length === 1) {
        return "";
    } else {
        for (let i = 1; i < inputString.length; i++) {
            outputString = outputString + inputString[i];
        }
        return outputString;
    }
};

print(stringRecursion("1103101")); // => will print "eEeEoO-eEoOeE"

More Recursion!

Using numbers with recursion doesn't just have to be arithmetic, although that is a pretty nice use for it. This example of recursion doesn't do any fancy arithmetic but it still has number parameters!

import { print } from "introcs";
 
let iNeedCoffee = (hoursLeftInDay: number, numberOfCups: number): number => {
    if (hoursLeftInDay === 0) {
        print("It took me " + numberOfCups + " cups of coffee but I made it through the day!!");
        return numberOfCups;
    } else {
        print("The day's still not done! Drink more coffee!!!!!");
        return iNeedCoffee(hoursLeftInDay - 1, numberOfCups + 1);
    }
};

What's going on here? The first thing we know is that we're taking in two numbers, one for the number of hours and one for cups of coffee. We also know we're returning a number.

To figure out what's happening, we'll start with our base case! When there are no more hours in the day I'm not going to keep drinking coffee, so I'll just print out how many cups I drank. Since printing and returning are not the same, I'll also need to return this number.

Next up, we'll think through the recursive case. If we get to this point, we know we're not at the end of our function call since we end in the base case. In the recursive case of this function, we print a statement then return the result of calling our function again!

As we know, the key to calling the function in the recursive case is changing the arguments! For this function, we changed both our arguments by subtracting from hoursLeftInDay and adding to numberOfCups. Adding to numberOfCups helps us know how many cups we ended up drinking, but the real fun is subtracting from hoursLeftInDay, since this subtraction is what brings us closer to our base case and prevents infinite recursion!

Here's how we'd call this function starting with 2 hours left in the day and 0 cups of coffee:

iNeedCoffee(2, 0);

If we made this function call, here's the output we'd see printed:

The day's still not done! Drink more coffee!!!!!

It took me 2 cups of coffee but I made it through the day!!

When we first call the function, since 2 !== 0 we enter the else block, which is our recursive case. Here, we hit a print statement so we get our first line of printed output. Then we return iNeedCoffee(hoursLeftInDay - 1, numberOfCups + 1) This is a recursive call to our iNeedCoffee function, but we changed the arguments! Since we started with iNeedCoffee(2, 0) and now we're subtracting one from hoursLeftInDay and adding one to numberOfCups, replacing these with our adjusted arguments would look like iNeedCoffee(1, 1) Entering this call to the function, we know 1 !== 0 so we enter the recursive call again and repeat the steps of printing our statement then going through another recursive call in return iNeedCoffee(hoursLeftInDay - 1, numberOfCups + 1). Since our last call used 1 and 1 as arguments, when we adjust based on these values our new call will look like this: iNeedCoffee(0, 2) This is great! When we enter this function call we see that 0 === 0 so we can finally enter our base case! Doing so, we print out another statement and return our final value for the number of cups of coffee.

Comp 110 Recursion with Numbers/Strings