REC - Recursion (Lesson)

Recursion

Introduction

Recursion is a method that calls itself.

public void mystery (int n)
{

if (n > 1)
{
System.out.print(n);
mystery(n - 2);
}

else
{
System.out.print(n);
}
}

Notice in this mystery method, mystery is called again as part of the if statement. In order to call this method, we must call the method again.

All recursive methods have a base case. This is the condition that allows the recursion to end.

public void mystery(int n)
{

if (n > 1) //this is the line indicating the base case
{
System.out.print(n);
mystery(n-2); //this is the recursive call
}

else
{
System.out.print(n);
}
}

In the mystery method, 1 is the base case since the method will stop calling itself when the parameter is 1 or less. If we did not have a base case, we would have an infinite recursive method.

Tracing a Recursive Method

To trace a recursive method, we create a stack where we start at the bottom and work our way up and then back down. For example, let’s try our mystery method when n = 10.

public void mystery(int n)
{

if (n > 1)
{
System.out.print(n);
mystery(n - 2);
}

else
{
System.out.print(n);
}
}

mystery(0) = 0
mystery(2) = 2mystery(0)
mystery(4) = 4mystery(2)
mystery(6) = 6 mystery(4)
mystery(8) = 8 mystery (6)
Start here mystery (10) = 10 mystery(8)

Once we reach the base, in our case mystery(0), we can start at the top and substitute our values back in:

mystery(0) = 0
mystery(2) = 2 mystery(0) = 2 0
mystery(4) = 4 mystery(2) = 4 2 0
mystery(6) = 6 mystery(4) = 6 4 2 0
mystery(8) = 8 mystery (6) = 8 6 4 2 0
mystery(10) = 10 mystery(8) = 10 8 6 4 2 0