R.1: RECURSION

OBJECTIVE

I can:

determine the result of executing recursive methods

Recursion is when a method calls itself like this:

This method will print out "This is the method that never ends!" and then call itself, which will print out the message again, and then call itself, print the message, call itself, print the message, call itself, print the message, and so on.

This is called infinite recursion, which is a recursion that never ends.

Of course, this particular method is not very useful.

WHY USE RECURSION?

Recursion is most useful when it is used to solve problems where the structure of the problem repeats.

For example, what if you wanted to find out how much space on your computer uses.

You could add up the sizes of all files in that folder, but folders can also contain subfolders and subfolders can contain subfolders...

So you will have to repeat the procedure (method) for each subfolder and the subfolders within subfolders.

Recursion can also be used to create fractals.

A simple example of a fractal is Sierpinski's triangle in which you subdivide a triangle into 4 new triangles as shown below.

The same procedure can be performed with each new triangle (except the center one).

Recursion can also be used to traverse String, array, and ArrayList objects, much like a loop.

In fact, any recursive solution could be written with iteration (loops) instead.

FACTORIAL METHOD

The following video introduces the concept of recursion and tracing recursion with the factorial method:

The method factorial below calculates the factorial of a number.

If you have never heard of factorials in your math class, they are just products indicated by an exclamation mark.

For example, "four factorial" or 4! means 1 x 2 x 3 x 4 = 24.

We can do this procedure with a recursive method!

Notice in the method below that a number is defined as 1 if n == 0.

I tested out this factorial method in the following code:

BASE CASE

Every recursive method must have at least one base case which halts the recursion.

This is usually an if statement that causes the recursion to stop by just giving an answer without needing a recursive method call.

You could think of the base case as the "simplest case" where you can just give the answer right away.

For example, the base case for the factorial method has a way to stop the recursion (stop calling itself) when n is equal to 0 because it just returns 1.

Note: a recursive method can have more than one base case.

TRACING RECURSIVE METHODS

In Java, the call stack keeps track of the methods that you have called since the main method executes.

A stack is a way of organizing data that adds and removes item only from the top of the stack.

A great analogy is a stack of cups.

You can grab cups from or add more cups to the top of the stack.

When you are executing one method (method a) and it calls another method (method b) the method call is placed on the stack along with information about where it was called from.

This tells the run-time where to return to when the current method finishes executing.

When method b finishes executing the run-time pops the method b off of the call stack and returns execution to the next line to be executed in method a.

Consider the following class definition:

The code above will cause a run-time error of division by zero when it runs.

The main method calls the method test1 (at line 20) which calls the method test2 (at line 6) which has the divide by zero error (line 14).

This can be seen in the call stack below which shows the call stack from the top (most recent method) to the bottom (first method call).

When a method calls itself the new method call gets added to the top of the call stack.

Execution of the current method pauses while the recursive call is being processed.

Each recursive call on the stack has its own set of local variables, including parameter variables.

The parameter values progressively change in each recursive call until we reach the base case which stops the recursion.

Let's trace the execution of the factorial method below:

What happens when we call factorial(0)?

It will return 1 since n is equal to 0.

How about factorial(1)?

It will return 1 * factorial(0).

We already know that factorial(0) returns 1, but the computer won't remember that.

It will execute factorial(0) and return 1.

So, factorial(1) will return 1 * 1 which is 1.

How can you show what is happening in the recursive call?

The lines below show the call stack upside down (with the bottom of the stack, or the beginning at the top and the most recent call at the bottom) for a call to factorial(5).

This is a handy way to trace a recursive method on the exam and you will do much better on recursive problems if you practice doing it this way.

Once factorial(0) executes and returns 1 that value can be substituted back into the previous method call, starting at the top of the stack (shown at the bottom here) and working our way back to the bottom of the stack (shown at the top here).

So, factorial(5) returns 120.

Check out this Java Visualizer and step through the code.

SUMMARY

A recursive method is a method that calls itself.
Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.
Each recursive call has its own set of local variables, including the formal parameters.
Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.
Any recursive solution can be replicated through the use of an iterative approach.
Writing recursive program code is outside the scope of the course and AP Exam.
Recursion can be used to traverse String, array, and ArrayList objects.

EVIDENCE

1) Complete the following Google Form. This form must be 100% correct and includes released AP practice questions. To stop working and return later, hit submit! You can "edit your response" and continue where you left off.

R.1 Evidence

2) Create Your Own Assignment! Remember, the OBJECTIVE of this lesson is to be able to determine the result of executing recursive methods. What EVIDENCE can you present to prove that you can do this? Meet with Mr. C when you are ready to present. In other words, show me what you can do!

3) MC Exam Practice: This lesson has additional practice problems which can be found on the MC Exam Practice page with an answer key! Use ctrl + f to search for different objectives throughout the year. You could look at these questions now, or, save these practice questions for later and use them to review! The choice is yours.

Report abuse

R.1: RECURSION

OBJECTIVE

Recursion is when a method calls itself like this:

This method will print out "This is the method that never ends!" and then call itself, which will print out the message again, and then call itself, print the message, call itself, print the message, call itself, print the message, and so on.

This is called infinite recursion, which is a recursion that never ends.

Of course, this particular method is not very useful.

WHY USE RECURSION?

Recursion is most useful when it is used to solve problems where the structure of the problem repeats.

For example, what if you wanted to find out how much space on your computer uses.

You could add up the sizes of all files in that folder, but folders can also contain subfolders and subfolders can contain subfolders...

So you will have to repeat the procedure (method) for each subfolder and the subfolders within subfolders.

Recursion can also be used to create fractals.

A simple example of a fractal is Sierpinski's triangle in which you subdivide a triangle into 4 new triangles as shown below.

The same procedure can be performed with each new triangle (except the center one).

Recursion can also be used to traverse String, array, and ArrayList objects, much like a loop.

In fact, any recursive solution could be written with iteration (loops) instead.

FACTORIAL METHOD

The following video introduces the concept of recursion and tracing recursion with the factorial method:

The method factorial below calculates the factorial of a number.

If you have never heard of factorials in your math class, they are just products indicated by an exclamation mark.

For example, "four factorial" or 4! means 1 x 2 x 3 x 4 = 24.

We can do this procedure with a recursive method!

Notice in the method below that a number is defined as 1 if n == 0.

I tested out this factorial method in the following code:

BASE CASE

Every recursive method must have at least one base case which halts the recursion.

This is usually an if statement that causes the recursion to stop by just giving an answer without needing a recursive method call.

You could think of the base case as the "simplest case" where you can just give the answer right away.

For example, the base case for the factorial method has a way to stop the recursion (stop calling itself) when n is equal to 0 because it just returns 1.

Note: a recursive method can have more than one base case.

TRACING RECURSIVE METHODS

In Java, the call stack keeps track of the methods that you have called since the main method executes.

A stack is a way of organizing data that adds and removes item only from the top of the stack.

A great analogy is a stack of cups.

You can grab cups from or add more cups to the top of the stack.

When you are executing one method (method a) and it calls another method (method b) the method call is placed on the stack along with information about where it was called from.

This tells the run-time where to return to when the current method finishes executing.

When method b finishes executing the run-time pops the method b off of the call stack and returns execution to the next line to be executed in method a.

Consider the following class definition:

The code above will cause a run-time error of division by zero when it runs.

The main method calls the method test1 (at line 20) which calls the method test2 (at line 6) which has the divide by zero error (line 14).

This can be seen in the call stack below which shows the call stack from the top (most recent method) to the bottom (first method call).

When a method calls itself the new method call gets added to the top of the call stack.

Execution of the current method pauses while the recursive call is being processed.

Each recursive call on the stack has its own set of local variables, including parameter variables.

The parameter values progressively change in each recursive call until we reach the base case which stops the recursion.

Let's trace the execution of the factorial method below:

What happens when we call factorial(0)?

It will return 1 since n is equal to 0.

How about factorial(1)?

It will return 1 * factorial(0).

We already know that factorial(0) returns 1, but the computer won't remember that.

It will execute factorial(0) and return 1.

So, factorial(1) will return 1 * 1 which is 1.

How can you show what is happening in the recursive call?

The lines below show the call stack upside down (with the bottom of the stack, or the beginning at the top and the most recent call at the bottom) for a call to factorial(5).

This is a handy way to trace a recursive method on the exam and you will do much better on recursive problems if you practice doing it this way.

Once factorial(0) executes and returns 1 that value can be substituted back into the previous method call, starting at the top of the stack (shown at the bottom here) and working our way back to the bottom of the stack (shown at the top here).

So, factorial(5) returns 120.

Check out this Java Visualizer and step through the code.

SUMMARY

A recursive method is a method that calls itself.

Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.

Each recursive call has its own set of local variables, including the formal parameters.

Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.

Any recursive solution can be replicated through the use of an iterative approach.

Writing recursive program code is outside the scope of the course and AP Exam.

Recursion can be used to traverse String, array, and ArrayList objects.

EVIDENCE

1) Complete the following Google Form. This form must be 100% correct and includes released AP practice questions. To stop working and return later, hit submit! You can "edit your response" and continue where you left off.

R.1 Evidence

2) Create Your Own Assignment! Remember, the OBJECTIVE of this lesson is to be able to determine the result of executing recursive methods. What EVIDENCE can you present to prove that you can do this? Meet with Mr. C when you are ready to present. In other words, show me what you can do!