Intro to Recursion

 To get any deeper into algorithms on lists of numbers like we’ve seen, we have to at some point tackle the elephant in the room that is left unexplained in the last article: how we sort. But to get to sorting, we need to undergo a fundamental shift in how we think. Normally, a teacher will say it’s very bad form to define a thing in terms of itself; that may certainly be true in English class, but not in math or computer science. In math and computer science, we define problems in terms of themselves all the time with no issues at all: no wrong answers on account of that style (although mistakes can happen), no angry teachers, nothing like that.

We call these self-referential problems “recursive.”

In math, for instance, the function:

• f(0) = 0
• f(1) = 7
• f(2) = 27
• f(n) = f(n-1) / 2 + 3 * f(n-2)

is perfectly fine because it’s recursive.

In explaining recursion, I’ll point to math for two very famous sequences which are both classically defined this way: using addition, the Fibonacci sequence; and using multiplication, the factorial.

You have probably heard of Fibonacci in the context of breeding rabbits: given that you start with a pair of newborn rabbits, and they never die; and pregnancies last one month, and rabbits can breed after their first month, how do you figure out how many rabbits will exist in a certain amount of time?

• At time 0, there is 1 pair, the original immature pair
• At time 1, there’s still 1 pair, but now they’re mature and have just bred
• At time 2, there are 2 pairs
• The original
• Their baby offspring
• At time 3, there are 3 pairs
• The original
• Their first offspring
• Their new babies
• At time 4, there are 5 pairs
• The original
• Their first offspring pair
• The offspring of this pair
• Their second offspring pair
• The offspring of this pair
• And so on

How do you formulaically state how many pairs exist?

First, you have the initial conditions that at months 0 and 1, rabbit(x) = 1; there is 1 pair in month 0, and one pair in month 1. Then, notice that for months 2 and beyond, the number of rabbits is rabbit(x-1) + rabbit(x-2)—that is, how many pairs there were last month, plus how many there were two months ago. This is because a rabbit is pregnant for one month, and then baby rabbits can breed once they’re one month old (and they never die). Classically, the problem is about a year later. Let’s check it out!

• When we start, there’s 1 pair
• A month later, there’s 1 pair
• 2 months later, 2 pairs
• 3 months later, 3 pairs
• 4 months later, 5 pairs
• 5 months later, 8 pairs
• 6 months later, 13 pairs
• 7 months later, 21 pairs
• 8 months later, 34 pairs
• 9 months later, 55 pairs
• 10 months later, 89 pairs
• 11 months later, 144 pairs
• A year later, 233 pairs!

This method of calculating the number of pairs works, but it’s inefficient for a reason we’ll cover in a later article.

Now, let’s do something similar, but with multiplication.

Let’s say a class includes no students. How many ways are there to form a line including no students? One way—[]. Now add Alice; how many ways can Alice stand in line? One way—[Alice]. Now add Bob. Two ways—[Alice, Bob] or [Bob, Alice]. Now add Charlie. How many ways? 6—[A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A].  If Dave joins the class, there are 24 ways; if Ellie joins the class, 120; if Finn joins, 720; if George joins, 5040. By the time Jenny joins the class, there are more than 3 million ways to stand in line.  By the time Zayden joins, the class, there are about 2000 times as many ways to stand in line as there are total cells in all people alive.

Mathematically, the function that counts the number of orderings is called the factorial function, written with ! (so n! is read as “n factorial” or “the factorial of n”) and means 1 times 2 times 3 times 4 times… up to n. We can define this as n! = n*(n-1)!

Notice how in both the additive Fibonacci case and the multiplicative factorial, we define the problem (factorial of 7, 12^th Fibonacci, etc.) in terms of smaller versions of that same problem. Factorial of 7 is 7 times factorial of 6; and Fibonacci of 12 is the sum of Fibonacci of 10 and Fibonacci of 11. Factorial of 6, in turn, depends on knowing factorial of 5; and Fibonacci of 10 requires knowing F(8) and F(9), and Fibonacci of 11 requires knowing F(9) and F(10). We keep building and solving self-similar problems, until we get to a problem we solve without this self-similarity because it’s small or easy enough.

For Fibonacci, it’s the initial-month conditions:

• F(0) is 1, the initial baby rabbits
• F(1) is still 1, the now-grown rabbits

For Factorial, either of the following works:

• 0! Is 1
• 1! Is 1

One place where beginning coders fail—and then get welcomed as “real developers” because you’ve suffered through this rite of passage—is in forgetting that all recursive problems need to have at least one stopping condition for which the answer is known without recursion, and that each successive problem (Fact(10) needs Fact(9) needs Fact(8) needs Fact(7) and so on, until Fact(1) or Fact(0) is given as 1) must in some way get closer to the stopping condition(s) than problems that came before it. Failure to both define and approach a stopping condition will produce the ceremonial first “StackOverflowError,” which every programmer must experience. (This is, by the way, the reason the website has that name.)

Make sure you have a great understanding of this concept before you ever move on to sorting. Call your friends or family into the room and explain it. Until they understand it, don’t move on. (This is because a lot of sorting is, at a high level, “to sort, divide, sort each piece, and put them together”—that is, the definition of, say, “sort(10)” requires you to “sort(5)” twice and put them together. In other words, a lot of sorting is, fundamentally, recursive.)

A much better search

 Imagine for a second we have an array, and we want to find a particular number, and we want to do it more efficiently than the linear search: there’s a row of lockers, and is it in locker #0? No. Ok, is it in locker #1? No. Ok, is it in locker #2? No. Ok, is it in locker #3? Yes? Ok great, you found it!

To do better, we first need to guarantee the array is sorted. There are many sorting algorithms which we’ll go over soon, but for now, let’s just be hand-wavy, and assume that somehow, the array was sorted. You should not care in which direction, ascending or descending, it was sorted.

This method that looks for something through a sorted collection is called “binary search”, not because of 100100110101101, but because it splits things in half.

You probably do this (or your parents did), if you ever use a phone book. Imagine you’re looking for someone whose last name is “Kelly.” K is kind of near the middle of the alphabet, so you open the phone book in what you think the middle is. You’ve landed on a page full of “Ingleton” records. Not far enough into the Ks, but you do know something. Your “Kelly” friend is not in the part of the book from the beginning until “Ingelton,” since “K” comes after “I.” So you flip to the next page after “Ingleton,” and treat that as “page 1”. From there, you flip forward some amount trying to find “Kelly”, and you land in “Martinez.” Oops, too far. “Kelly” lies somewhere between “Ingelton” and “Martinez,” so you know two things: you shouldn’t waste time looking earlier in the alphabet than “Ingleton,” or later than “Martinez.” From “Martinez,” you flip backward and get to “Jones.” Now, again, you’re before “Kelly,” but your region to search through keeps shrinking. Now, it only makes sense to search between “Jones” and “Martinez.” You flip one page after Jones, and you find your friend’s number.

Harvard’s Dr. David Malan, in their CS50 introductory class, does this with a physical phone book every time he teaches the class, literally tearing the book in half (as opposed to just ignoring the irrelevant parts, where the answer cannot be) in the alphabetized phone book because he wants to find someone.

Imagine you have 1000 items, and you need to find item 371 to figure out what it is. You could go to item 1, then 2, then 3, then 4… then 370, then 371, and you’d know the answer, but this other way is much quicker. You go to item 500 in the middle right away. 371 is less than 500, so you immediately give yourself permission (since items are somehow sorted) to ignore 501-1000. The middle of your new search space is 250 (from 1 to 500), so you look there. You’ve looked at 2 items.  Now, you look just between 251 and 500, at the middle of that—376. Now, you’ve looked at 3 items. Your item is somewhere between 250 and the middle, so you ignore the top half. Now, the middle of the new range is 313. Your item is after 313, but before 376, so you ignore everything else. Then, the new middle is 345. Your item is between 345 and 376, so you ignore everything else. You look at the new middle—361—and decide your item is above it, so you ignore everything else. Your new range is now just 369 to 376. The middle is 373, so your item is in the lower half just from 369 to 373. You look in the middle, and you find your item.

Look how much quicker that was—500, 250, 376,  313, 345, 361, 373, found 371—than actually examining 370 previous items and failing to find it. This is why binary search is so powerful, and almost every “find me XYZ in a huge collection” in technology these days uses it. My best friend’s phone number is saved under her last name, “Elwood.” If I didn’t know that number by heart and still needed to look her up to call her, if I were to look for “Elwood” in my phone’s contact list, then examine the code Android is using to give me back her number, I am nearly certain that it would be doing this.

Don’t start thinking about binary search in code terms just yet. First, look at the pseudocode.

function binarySearch(array, target):

    low ← 0

    high ← length(array) - 1

    while low ≤ high do:

        mid ← low + (high - low) / 2

        if array[mid] == target then:

            return mid   // Target found at index mid

        else if array[mid] < target then:

            low ← mid + 1   // Search right half

        else:

            high ← mid - 1  // Search left half

    return -1   // Target not found

Understand how the pseudocode works—match it to finding “Kelly” or “371” in those stories—and then try it with a very small (maybe 10 items, if not less) sorted array. Try it out when you both can guarantee you’ll find the item and when you can guarantee you won’t. Call a friend, a parent, a sibling, a significant other into the room, and demonstrate the algorithm to them. Only once you’re confident you can explain it, implement this Java:

public class BinarySearch {

    public static int binarySearch(int[] arr, int target) {

        int low = 0;

        int high = arr.length - 1;

 

        while (low <= high) {

            int mid = low + (high - low) / 2;

 

            if (arr[mid] == target) {

                return mid; // Target found

            } else if (arr[mid] < target) {

                low = mid + 1; // Search right half

            } else {

                high = mid - 1; // Search left half

            }

        }

        return -1; // Target not found

    }

 

    public static void main(String[] args) {

        int[] arr = {1, 3, 6, 8, 10};

        int target = 8;

        int result = binarySearch(arr, target);

 

        if (result != -1) {

            System.out.println("Value found at index: " + result);

        } else {

            System.out.println("Value not found");

        }

    }

}

Linear Search

 The simplest way to go through a collection of things and see if any one of them is the one you’re looking for—however inefficient it might be (spoiler alert: very)—is simply to check each element.

An array is a contiguous grouping—that is, next to each other in memory, rather than all over the place—of some fixed length of elements of the same type.

Suppose for simiplcity (though this can extend beyond this simplest case) that we just have an array of integers, int[] nums = new int[10];

Here, nums is an array of 10 integers—whole numbers that range from about -2,147,000,000 to +2,147,000,000, where, if no value is specified, the default is 0.

Initially, in a very literal sense, the memory looks like

0

0

0

0

0

0

0

0

0

0

 
But now, suppose we give those 10 spots some non-zero values:

0

10

37

28

1000

457

-29

398

-2789

23798

From here, suppose we want to figure out if the number 1000 is in the collection. We are humans, so we can see the whole collection at once and determine that 1000 is in the 5^th spot, labeled as nums[4] because computers start counting from 0, so the first position is nums[0]; that nums[0] happens to have the value 0 inside it, at this point, is pure coincidence.

Computers can’t see the whole collection at once, so the best we can do on a computer is use a loop to check through each position, as if we’re opening a series of 10 lockers one by one.

Is it in position 0? No.
Is it in position 1? No.
Is it in position 2? No.
Is it in position 3? No.
Is it in position 4? Yes!—now we can stop because we’ve found it, and either we report that we found it (as a boolean with the value true), or we report where we found it (as an int with value 4).

This basic algorithm is called linear search. “Linear” here may evoke the idea of going down a line of lockers to check them all, but that’s not where it comes from. It comes from the fact that, checking one at a time, without assuming anything (i.e., that something is sorted), in the worst case, the number of failures this algorithm might have before it finds a needle in the haystack grows linearly (like, for example, the function f(x) = 3x + 2) with the size of the haystack. If the array is suddenly 20 (double the size), then I might have to check 20 places. If it shrinks down to 5, then I might have to check 5 places, and so on. (This is as opposed to, for instance, tripling the number of lockers 9x-ing the number of checks. In linear algorithms, tripling the size of the input only triples the number of steps.)

This is a good searching algorithm in that it’s easy to learn, but it isn’t a very fast one. Soon, we’ll learn a much faster way to find things (leaving aside the complication of sorting, which we’ll take for granted at this point), called a binary search. Happy searching!

Implementing Dog

 In our last article, I mentioned that there are two kinds of constructors—those taking arguments and those that don’t. The one that doesn’t have any arguments exists by default, unless others are created, in which case it must be created explicitly.

To understand constructors, we need to learn a new keyword in Java: this.

Suppose I have a Dog class.

I want that class to have:

1. My dog’s name
2. My dog’s owner’s name
3. My dog’s age
4. My dog’s breed

This is because name, age, owner’s name, and breed are fundamental to who a dog is.

Suppose I want to also be able to let my Dog bark—simply by printing “woof!” to the screen

I can do this by creating a class to represent my dog.

public class Dog{

public static void main(String[] args){
}

}

So far, everything looks familiar, right? Now, for the new parts.

We’ve created variables inside methods before, like this:

public static void doSomething(){
        int x = 0;
}

For a reason we’ll address very shortly, that x only belongs to doSomething, not to anything else around it.

We want a way to make the Dog’s age, breed, owner, etc., intrinsic to the Dog, and so visible to all of the Dog class. For this, we need what are called instance variables—those declared not inside a method (like x), but only inside a class.

That looks something like

public class Dog{

        public String name;
        public  String owner;
        public int age;
        public String breed;

         public static void main(String[] args){
         }

}

By placing those variables there, we make them a part of any (every) Dog, not just one or two methods, and not just one or two Dog objects.

Obviously, it does us no good to have variables but not be able to look inside them and know their values, or change them. For this, we need some methods called getters and setters. These, appropriately, get back the values of variables, or set them to be certain values. The names these methods take should correspond to that. For instance, setAge sets the Dog’s age; getOwner() gets the owner of a Dog; and so on.

Fully implemented, the getters and setters look something like this:

public class Dog {

    private String name;

    private String owner;

    private int age;

    private String breed;

public Dog(String name, String owner, int age, String breed) {

        this.name = name;

        this.owner = owner;

        this.age = age;

        this.breed = breed;

    }

public Dog(){

}

    public String getName() {

        return name;

    }

    public void setName(String name) {

        this.name = name;

    }

    public String getOwner() {

        return owner;

    }

    public void setOwner(String owner) {

        this.owner = owner;

    }

    public int getAge() {

        return age;

    }

    public void setAge(int age) {

        this.age = age;

    }

    public String getBreed() {

        return breed;

    }

    public void setBreed(String breed) {

        this.breed = breed;

    }

}

All these methods make use of the “this” keyword for a rather simple reason: the parameter’s name in the constructor or setter is the same as the property’s name. What we mean by this is, for example, with

    public void setBreed(String breed) {

        this.breed = breed;

    }

This means, “Set the breed field of the current Dog to be the parameter we just passed”, and likewise with the others. We do this since it would get very confusing if the parameter name and the field name were the same, without this modification. As you’re getting used to constructors and setters, I highly recommend doing things by hand and color-coding—perhaps with pens or highlighters—what it is you mean for your code to do before actually writing it. And remember: direction matters in assignment, and flows from right to left!

Now, implementing the last thing on my wishlist is trivial: Into the Dog class, I add

public void sayWoof(){
        System.out.println(“Woof!”);
}

and I’m done! All we need now is a main method (public static void main(String[] args), of course!) and we’re all set

Comments

Now is a good time to look at an essential part of coding that gives no instructions at all. In fact, the JVM explicitly does nothing with these lines. Just as you might see notes in the margin of a novel or textbook (explaining why something is important, connecting something you just read to something else, reminding yourself to come back later, etc.), you can, and should, do the same in code.

Java calls these little notes to yourself, without any bearing on the execution of the program, “comments.” The process of writing them is called “commenting” or “documenting” and, even early on, is just as essential to getting code done right as solving the problem correctly or solving the correct problem.

Every language has some delimiter that it looks for in lines of code, where, if it finds it, it ignores whatever is inside as a comment, not an instruction. In some languages, it’s ; or ;; (but recall that in Java, ; ends a statement which is code); in others, it’s # or ##. Java has two comment styles, based on different lengths: for short comments that take up just one line, and for longer multi-line comments. You can, if you wish, write a multi-line comment in that style, or with a bunch of single-liners.

Java’s single-line comments are indicated by //-- two forward slashes. Anything else in the line after two forward slashes will be ignored and treated as a comment, not an instruction. Multiline comments start with /* and end with */. Anything inside there is considered the comment.  

As you progress along your software development journey, you’ll become more and more aware of what needs comments and how detailed they should be. Just remember—you’re leaving notes to your future self (or someone else you may not know) about what the code does so that they can keep using, changing, or fixing it in the future.

Here, for example, is a well-written, functional Calculator class, missing any comments:

public class Calculator {

    public int add(int a, int b) {

        return a + b;

    }

    public int subtract(int a, int b) {

        return a - b;

    }

}

And now here is the same class, but with descriptive comments:

public class Calculator {

    /* This method adds two integers */

    public int add(int a, int b) {

        // Return the sum of a and b

        return a + b;

    }

 

    // This method subtracts the second integer from the first

    public int subtract(int a, int b) {

        return a - b; // Return the difference

    }

}

These examples are very simple, but even from something at this level, you can see how comments make it easier to know what to expect before reading a method in depth.

Generally, IDEs—at least IntelliJ—color-code things based on what they are. Reserved words like “public” or “static” or “int” are one color; method names like toString() are another color; properties, like “breed” in Dog.breed are the same color as method names; String literals, like “I like pizza” are a different color, etc. This helps someone just skimming the code know what things are, even at skimming speed. Most text, as in instructions, is just plain black. But comments are different. Most of the time, they appear as gray, but if you start your comments with certain words like “TODO” (not necessarily all uppercase) or “fixme” (not necessarily all lowercase), then the IDE will help you by color-coding those comments differently than regular ones, or anything else (usually in bright blue), to help draw your attention to the fact that you haven’t finished something, or that you’ve found a bug somewhere and need to fix it.

It takes time to learn how to write good comments, so don’t worry if you think you’re writing comments that are obvious—like, above a line “int x = 0;” writing “// this is an integer called x and its value is 0”—in the beginning. Those comments are an important stepping stone toward really good ones. As an exercise, go back through all the code you’ve written so far and write some comments.

And remember that comments are changes, so re-run your programs to test them and make sure they still work, since you might have accidentally commented out something you didn’t intend to!

Method parameters

 The last element of the signature we’ll discuss (skipping over the name, which can be anything as long as it doesn’t start with a number, just like naming conventions for variables) is the parameter list.

As with the static modifier, it can have information there or not. Just like “public static int foo()” and “public int foo()” are different (and the inclusion or not of the static modifier means something), the same is true of the parameter list.

Methods are not required to have parameters, but even if they don’t, you still need to have the () with nothing inside them—and that () communicates the fact that the method doesn’t take anything in.

You can have as many parameters as you want (or none at all, depending on what you are doing) in your methods, but beware of a few considerations:

• The order you put them in the signature is the order they have to be passed in when the method is called.
• You must pass in every argument a method expects to receive, in the proper order, or you will get an error.
• Passing in arguments to a method not expecting any will result in an error.
• Not passing arguments to a method expecting them will result in an error.
• Passing the wrong type will result in an error.

Here’s an example of a method without any parameters:

public class Greet {

    public void sayHello() {

        System.out.println("Hello!");

    }

    public static void main(String[] args) {

        Greet greeter = new Greet();

        greeter.sayHello();

    }

}

Here’s an example of a method with parameters that will work:

public class Adder {

    public int add(int a, int b) {

        return a + b;

    }

 

    public static void main(String[] args) {

        Adder adder = new Adder();

        int sum = adder.add(3, 5);

        System.out.println("Sum: " + sum);

    }

}

This works because adder.add() expects two integers, and it gets 3 and 5.

And here is an example of something that won’t work—notice the addition of the integer and the String, when the method expects two integers.

public class Adder {

    public int add(int a, int b) {

        return a + b;

    }

    public static void main(String[] args) {

        Adder adder = new Adder();
        int sum = adder.add(3, "5");
        System.out.println("Sum: " + sum);

    }

}

In Java, objects and primitives may be parameters, but, unlike other languages, methods (which other languages call functions) cannot be. 

Return types

 The next thing that comes up in a method signature (after the access modifier and the static flag) is the return type. At a high level, there are two return possibilities: nothing and something.

You might have a method that returns nothing, but it is never allowable to not have a listed return type (except in the case of a constructor). If your method returns nothing, the correct return type is void.  (Recall that we have “public static void main(String[] args)”). If your method returns void, you won’t return anything. You can have a “return” statement—more on that in a bit—in a void method, just as an “if I get here, stop and exit” condition, but there won’t be a value attached.

That early exit might look like

public class EarlyExitDemo {

    public void printPositive(int number) {

        if (number <= 0) {

            return;

        }

        System.out.println("The number is positive: " + number);

    }

}
 
Here, if the passed-in number is negative or zero, the program just gracefully exits by that “return” statement.

This is not required. Recall, again, HelloWorld written only in the main method, as simply as possible. The main method is void, and there is no return, even for an early exit as above:

 

public class HelloWorld {

    public static void main(String[] args) {

        System.out.println("Hello, World!");

    }

}  

However, if your method has some other declared return type—which can be any primitive or any object—then if you fail to return a value of that type, you will get an error.

Look at this code:

public class SimpleReturn {

    public int goodDoubleValue(int number) {

        return number * 2;

    }

}

This is correct. The return type expected is an integer, and we return 2 times an integer, which is an integer.

If instead the code had, for example, saved number * 2 into a variable but forgotten to return it, that would produce an error. Look at an example of that below:

public class SimpleReturn {

    public int badDoubleValue(int number) {

        int result = number * 2;

    }

}

When writing in an IDE, they can be especially helpful at flagging errors like this one!