Method Calls and Recursion

Contents

keyboard_tab

The course is part of this learning path

Start course
Overview
Difficulty
Intermediate
Duration
1h 19m
Students
84
Ratings
5/5
starstarstarstarstar
Description

This course looks at methods, which are named, self-contained blocks of code that you can call upon to help solve problems for you. We'll then take a look at some projects which will put methods into practice.

Learning Objectives

  • Understand the fundamentals of writing your own methods
  • Learn how to classify methods by their return types as well as their parameters
  • Learn about parameter passing schemes that are used by programming languages to determine how methods treat their parameters
  • Explore method overloading and two-dimensional arrays

Intended Audience

  • Beginner coders or anyone new to Java
  • Experienced Java programmers who want to maintain their Java knowledge
  • Developers looking to upskill for a project or career change
  • College students and anyone else studying Java

Prerequisites

This is a beginner-level course and can be taken by anyone with an interest in learning about Java.

Transcript

So far in this course, you've seen how to write your own methods to perform operations for you, and how to use your methods by calling or invoking them. Specifically, we've called the methods from the main method. But in reality, any method can call another method. Let me show you what I'm talking about. Let's create a file called MethodCalls. So, we'll go over here, 'New', 'Java Class', MethodCalls right there. All right. And of course, our main method. Here we go. All right. Now what I would like to do is I'm going to create a method called doSomething, and then I'm also going to create a method called getSomeValue. So, I think first we're going to create getSomeValue and that one's just going to return a literal. So, 150. So again, it's trivial pretty much. It's just for demonstration purposes. Now, doSomething is going to be a void method, and we're going to call that actually from main. 

So, we're going to call this right here. There we go. And I'm going to put this right down here, doSomething(). System.out.println(" In doSomething!"); and then I wanted to do this. So, int result = get SomeValue(); right there. And then system.out.println  I'll say (" result: " + result);  right there. Okay. So, we can see that the main method, which is the entry point of our application right here calls the method name to doSomething. Then the doSomething method uses the getSomeValue method right here. So, it makes an invocation or a call to the getSomeValue method right there in order to obtain a value, specifically. Obviously, the value itself is trivial, and it's just for demonstrative purposes. Let's run this program and see what we get. 

So, if I 'right' click 'MethodCalls', go to 'Run', and there we go. It says in doSomething because from main it called doSomething, and then it called this right here, println method within doSomething. And then we obtain the value 150, and then print that out. So, that's why it says result is 150. Great. So, we can see that the main method again calls doSomething, and then doSomething calls getSomeValue. And these chains can go on and on and on as much as we need. It's important to note that in the doSomething method, there are not one but two method calls. The println method is also a method that we are calling. The getSomeValue method is however, of course, a user-defined method that we write at ourselves. So, we've established that any of our methods can call other methods.

So, what then is recursion? Recursion is when a method calls itself. In order for a method to be recursive, it needs at least one of each of two things: A base case where there's no recursion, and a recursive case where there is recursion. It can have multiples of these, but it has to have at least one of each. So, let's write some more code to demonstrate it. I'm going o close this file right here, MethodCalls, and create a new file called CountDown. 'Right'-click, 'New', 'Java Class', CountDown. public static void main() And then we're also going to have our CountDown method, public static void countDownFrom() end countDownFrom. 

And we're going to call this from main. So, countDownFrom(10) and here is how this is going to work. So, as long as the number that's passed in is greater than or equal to zero, we're going to do this. System.out.println print the number out. And then we re going to call countDownFrom which is the same method we are in, we're going to go (num - 1) So, the idea here is that if it gets into the sub-statement, it's got to be at least zero. And then it would just call it the once and then stop because the next time, it would be a -1 here and then it won't satisfy the condition. But let's say, it's a 10 like we started with up here. It will go 10, 10 >=  0. That's true. Print out the 10, and then called countDownFrom this right here on 9. Pretty cool. Let's run it to see what it does. So, 'right' click and we're going to go to 'Run'. And as expected 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 and 0, because we included that. Pretty cool. 

The recursive case is pretty obvious. That's the call countDownFrom that we're moving towards this base case right here. The base case though is implicit. So, it can be explicitly spelled out in many cases it is, but again, this is called an implicit base case. It's clear that when the value goes below zero that it becomes negative, the if statements, condition is no longer true. So, the method will no longer be called. So technically, the base case or cases, in this case is a range of values. So, if you pass in a negative number starting from the beginning or simply when the recursive calls reach -1, the base case is satisfied, and no more recursive calls occur. One question might be- Couldn't we just use a for loop for this? The answer is- absolutely. In fact, for this particular problem, using a loop is much better. It's more efficient, and the code is easier to understand. But this is a good example because we can trace the method calls easily as it runs. 

So, you should see a diagram right now about MethodCalls, and this is what we're doing is we're tracing the calls of the method. Now you have to remember, we've got the method definition, and the MethodCalls, and what actually happens in memory are those different calls, and they become part of this call stack. So, the call stack is, like the name suggests, a stack, kind of like a stack of books that keeps track of the method calls that have occurred. Very briefly, you have to know that stacks are a much more complex and robust subject than what I'll describe here, but it would help you to know a few things about them. You can only add and remove items from the top of the stack. 

Also adding an item to a stack is called pushing an item onto the stack, and removing an item is called popping an item off of the stack. So, that terminology helps. Again, you can only access the top. And when you add the item, it's pushing when you remove it's popping. When any method is called, not just recursive methods, an activation record also called a stack frame is pushed onto the top of the stack. In general, stacks are data structures that can hold practically anything. But for methods, the runtime environment maintains the method call stack. And this stack doesn't hold dishes, trays, Pez candy, horses, cows, or donkeys, it holds activation records or stack frames. These activation records hold information about the particular method, call. 

The memory location of that call, the value of the parameters and local variables, where in the method the last instruction was executed etc. So, let's look at our example with countDownFrom. So, we initially called the countDownFrom(10) in the main method. Then there's a call to countDownFrom passing 9 to it from countdown with 10. Further, countDownFrom(9) calls countDownFrom(8). Then we have 7, then 6, then 5, then 4, 3, 2, 1, and finally 0. After  0 has reached, the condition is no longer true in the base case is reached. With the base case no longer true, the activation records are then popped off of the stack. So, countDownFrom(0), then countDownFrom(1), then countDownFrom(2), then 3, then 4, then 5, then 6, then 7 etc, etc, etc. And eventually, we make it down to countDownFrom(10), and then when that is popped off of the stack, we are left with main. And of course, main will be popped off the stack and the program will be complete. Awesome. So hopefully, you now have a better understanding of what happens when the methods are called and especially how recursion works. Nice. 

Before we move onto the next lecture, I have a challenge for you. In this same CountDown file, create a new method called countUpTo, but this time you'll take two parameters. It will start at one value the first parameter and count up to the second parameter, each passed in as an integer. You should use recursion to accomplish your goal. Make sure to call the initial method inside main on say, using the initial values 0 through 10, and observe what it does. You may comment out the countDownFrom method call in main to make it clearer if your program is working or not. As a hint, you would benefit from only changing one of the arguments as the recursive calls are made. Just make sure it causes the method calls to move toward the base case. So, pause the video, and come back when you're done or if you need some help. How did that go for you?

This one may be a little tricky, because recursion can sometimes be difficult to think about. But hopefully, you were able to complete this challenge. Let's work on it together. So, we're going to comment out this countDownFrom, and I'm going to actually create our new method here. public static void countUpTo(int from, int to) //end countUpTo that this really matters but it keeps it cleaner. Okay, here we go. And now in main, we have to call it from main or it's not going to work. So, countUpTo()  I'm going to go from (0, 10), so we can actually test it. Now what's this going to look like recursively? If ( from < = to ) System.out.println (from); and then call countUpTo(from) CountUpTo(from + 1,  and then just passing  to as the second parameter. 

So, whatever that value is it's going to remain consistent through the different method calls but from is going to actually change depending on which method call you're in. So, in different activation records, this from value will be different. So, there's an implicit base case here. If this is false, it will not execute what's inside the body of the if statement. Of course, let's run it. 'Right' click, 'Run'. And it does, in fact, count up from 0 to 10. So, another important note about recursion is that like repetition control loops, you could end up in a situation analogous to an infinite loop called infinite recursion. You may have discovered this when trying to write your code, and your code probably crashed. If it didn't, then you can always terminate the program. So, it doesn't try to keep running. So, there's when you're running your program, this little button here is red. So, you could actually just press that. All right. In the next lecture, we will discuss a side topic that will prove very useful for an upcoming project- the topic of 2D arrays. I'll see you there.

 

About the Author
Students
763
Courses
20
Learning Paths
4

John has a Ph.D. in Computer Science and is a professional software engineer and consultant, as well as a computer science university professor and department chair.

Covered Topics