Learn Programming With Java

Recursion - say what?!

Here you are going to learn one of the most fundamental concepts of programming: recursion. Let’s look at recursion in the context of a factorial. Do you remember what a factorial is? You may remember it from math class, and it looks a lot like this:

5! = 5 * 4 * 3 * 2 * 1 

4! = 4 * 3 * 2 * 1

3! = 3 * 2 * 1

Do you remember how to do that now? Well, the way a factorial works will give us a great example on how recursion works in Java.  Another way to write it would be:

N! = N * (N-1)!

In other words, using numbers, it looks a little bit like this:

5! = 5 * (5-1)!  which gives us  5! = 5 * (4)! , and finally 5! = 5 * 4!.

But, following the formula, we can also write  4!  as  4 * (4-1)!  which gives us 4 * 3!. We can plug this back into  5! = 5 * 4!  to get: 5! = 5 * (4 * 3!).

Wait, but looking at our new version, 3! can also use the formula! That will eventually get us to:  5! = 5 * 4 * (3 * 2!).  We can do the same thing over again with  2!.

Even if you're not a math person, you can see here that the factorial formula is used repeatedly. From a coding perspective, you can create a function that runs over and over just like this until you have a complete answer. How can you write a factorial in Java using operators? Let's try it out:

// define classes
class RecursionInJava {
    public static int factorial(int number) {
        n = n * factorial (n-1);
    }
}

If you look carefully at the line n = n * factorial(n-1), you will see that the the factorial method is called within itself. This is called recursion because the method runs over and over as it calls itself.

Do you remember conditional statements like if/else statements? They help a statement from going on until infinity by stopping the method for a reason. Why would you want to stop the method? When you do the factorial equation, it ends at 1. Essentially, you have to create a conditional statement that will end the recursion when n is 1.

This will do two things:

1. It will stop the factorial method from running after n reaches 1.

2. If the original number is 1, it will just return 1.

Let's see how how this looks:

// define classes
class RecursionInJava {
    public static int factorial(int number) {
        if (n == 1) return 1;
        else return n * factorial (n-1);
    }
}

Now, let's go back to the book example from the video.  📚 If you want to count the books in each category, subcategory, and so on, you need to make sure you take into account all the various layers. To address this, you can create a function that will go through the one level of categories. Then, once it’s finished, that function will call itself again, but this time making it work with the subcategories of one of the original categories. That iteration would go further and call itself again to process sub-subcategories. And so on, until a category at the level in question has no subcategories. This way you can go all the way down to the very last sub-level of each original category. And when a category has no subcategories, your function will return to your starting point.

Here's what the code that implements this looks like in Java:

Class BookStore (

// define a recursive function
public static int countBooks(Categories categories) {
    int c = 0;
    for category in categories {
        c += Category.numberOfBooks;
        countBooks(Category.subCategories);
        }
    return c
}

// call the recursive function
int numberOfBooks = countBooks(BookStore.categories);
System.out.println("The bookstore has "+numberOfBooks+" books");

Very efficient, isn't it?

In technical terms, recursion is an action that's initialized within itself. It keeps descending down layer upon layer, until a condition is met and then bubbles back up to the first layer.

Summary

• Recursion is an action that's initialized within itself.

• Recursion is used to go through layered structures.