Yorkville High School Computer Science Department
Yorkville High School Computer Science Department on Facebook  Yorkville High School Computer Science Department Twitter Feed  Yorkville High School Computer Science Department on Instagram

Yorkville High School Computer Science

ASSIGNMENTS: Hidden Figure - May 24, 2019

AP Computer Science :: Lessons :: Recursion

Barron's AP Computer Science

Chapter 7:
Pages 338 - 348


Fundamentals of Java
Chapter 12
Pages 455 - 467

Recursive Methods

A method is said to be recursive if it calls itself. This may sound weird, but we have actually used it before in the Fraction project with the gcf method. Most recursive methods can be written without recursion, but they are generally longer and more complex without it. Below is an example of a recursive method for determining factorials:

int factorial(int n) {
  if (n == 1)
    return 1;
  else
    return n * factorial(n - 1);
}

The factorial method calculates the product of all positive integers less than or equal to n, which it does by calling the factorial method over and over again. Here is how the same method could be written iteratively, or without recursion:

int factorial(int n) {
  int product = 1;
  for (int i = 2; i <= n; i++)
    product = product * i;
  return product;
}

The iterative method is a little longer, and actually seems a little more difficult to understand if we try walking through the recursive method. Let's try walking through our recursive method to see how it works.

Tracing Recursion

Let's follow each step of our recursive factorial method by finding 5!.

factorial(5)
   calls factorial(4)
      calls factorial(3)
         calls factorial(2)
            calls factorial(1)
            which returns 1
         which returns 2 * 1 = 2
      which returns 3 * 2 = 6
   which returns 4 * 6 = 24
which returns 5 * 24 = 120

The result of a recursive call isn't known until the final call returns a value. It then progresses back through the previous calls until the first call can return a value. It is very easy to create an infinite loop using recursion so it is important to make sure your calls will always return a value.

Fibonacci

The Fibonacci sequence is a famous sequence of numbers that looks like the following:

0, 1, 1, 2, 3, 5, 8, 13, 21,...

The sequence starts with 0 for number 0 and 1 for number 1, and each of the following numbers is the sum of the previous two. This is fairly easy to calculate using recursion:

int fibonacci(int n) {
  if (n == 0 || n == 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Try tracing out this method on paper. It will be a little different than with the factorial method since there are two recursive calls each time the method runs. Your trace should look more like a tree than the previous trace.

Yorkville High School Computer Science Department on Facebook Yorkville High School Computer Science Department Twitter Feed Yorkville High School Computer Science Department on Instagram