Introduction to Recursion
Introduction to Recursion
• So far, we have seen methods that call other
functions.
– For example, the main() method calls the square()
function.
main()
square()
• Recursive Method:
– A recursive method is a method that calls itself.
compute()
Why use Recursive Methods?
• In computer science, some problems are more
easily solved by using recursive functions.
• If you go on to take a computer science algorithms
course, you will see lots of examples of this.
• For example:
– Traversing through a directory or file system.
– Traversing through a tree of search results.
• For today, we will focus on the basic structure of
using recursive methods.
World’s Simplest Recursion Program
World’s Simplest Recursion Program
public class Recursion
{
public static void main (String args[])
{
count(0);
This program simply counts from 0-2:
System.out.println();
}
012
public static void count (int index)
{
System.out.print(index);
if (index < 2)
count(index+1); This is where the recursion occurs.
} You can see that the count() function
} calls itself.
Visualizing Recursion
• To understand how recursion works, it helps to
visualize what’s going on.
• To help visualize, we will use a common concept
called the Stack.
• A stack basically operates like a container of trays
in a cafeteria. It has only two operations:
– Push: you can push something onto the stack.
– Pop: you can pop something off the top of the stack.
• Let’s see an example stack in action.
Stacks
The diagram below shows a stack over time.
We perform two pushes and one pop.
8
2 2 2
Time: 0 Time 1: Time 2: Time 3: Time 4:
Empty Stack Push “2” Push “8” Pop: Gets 8 Pop: Gets 2
Stacks and Methods
• When you run a program, the computer creates a
stack for you.
• Each time you invoke a method, the method is
placed on top of the stack.
• When the method returns or exits, the method is
popped off the stack.
• The diagram on the next page shows a sample
stack for a simple Java program.
Stacks and Methods
square()
main() main() main()
Time: 0 Time 1: Time 2: Time 3: Time 4:
Empty Stack Push: main() Push: square() Pop: square() Pop: main()
returns a value. returns a value.
method exits. method exits.
Stacks and Recursion
• Each time a method is called, you push the method
on the stack.
• Each time the method returns or exits, you pop the
method off the stack.
• If a method calls itself recursively, you just push
another copy of the method onto the stack.
• We therefore have a simple way to visualize how
recursion really works.
Back to the Simple Recursion Program
• Here’s the code again. Now, that we understand stacks, we can visualize the
recursion.
public class Recursion1V0
{
public static void main (String args[])
{
count(0);
System.out.println();
}
public static void count (int index)
{
System.out.print(index);
if (index < 2)
count(index+1);
}
}
Stacks and Recursion in Action
count(2)
count(1) count(1)
count(0) count(0) count(0)
main() main() main() main() …
Time: 0 Time 1: Time 2: Time 3: Time 4: Times 5-8:
Empty Stack Push: main() Push: count(0) Push: count(1) Push: count(2) Pop everything
Inside count(0): Inside count(1): Inside count(2):
print (index); 0 print (index); 1
print (index); 2
if (index < 2) if (index < 2) if (index < 2)
count(index+1); count(index+1);
count(index+1);
This condition now fails!
Hence, recursion stops, and we
proceed to pop all functions off
the stack.
Recursion, Variation 1
What will the following program do?
public class Recursion1V1
{
public static void main (String args[])
{
count(3);
System.out.println();
}
public static void count (int index)
{
System.out.print(index);
if (index < 2)
count(index+1);
}
}
Recursion, Variation 2
What will the following program do?
public class Recursion1V2
{
public static void main (String args[])
{
count(0);
System.out.println();
}
public static void count (int index)
Note that the print statement
{
if (index < 2) has been moved to the end
count(index+1); of the method.
System.out.print(index);
}
}
Recursion Example #2
Recursion Example #2
public class Recursion2
{
public static void main (String args[])
{
upAndDown(1);
System.out.println();
}
public static void upAndDown (int n)
{ Recursion occurs here.
System.out.print ("\nLevel: " + n);
if (n < 4)
upAndDown (n+1);
System.out.print ("\nLEVEL: " + n);
}
}
Determining the Output
• Suppose you were given this problem on the final
exam, and your task is to “determine the output.”
• How do you figure out the output?
• Answer: Use Stacks to Help Visualize
Stack Short-Hand
• Rather than draw each stack like we did last time,
you can try using a short-hand notation.
time stack output
• time 0: empty stack
• time 1: f(1) Level: 1
• time 2: f(1), f(2) Level: 2
• time 3: f(1), f(2), f(3) Level: 3
• time 4: f(1), f(2), f(3), f(4) Level: 4
• time 5: f(1), f(2), f(3) LEVEL: 4
• time 6: f(1), f(2) LEVEL: 3
• time 7: f(1) LEVEL: 2
• time 8: empty LEVEL: 1
Computing Factorials
Factorials
• Computing factorials are a classic problem for
examining recursion.
• A factorial is defined as follows:
n! = n * (n-1) * (n-2) …. * 1;
• For example:
1! = 1 (Base Case)
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120
Iterative Approach
import javax.swing.JOptionPane;
public class FindFactorialIterative
{
public static void main (String args[])
{
int answer, n;
String nAsString = JOptionPane.showInputDialog("Enter a number: ");
n = Integer.parseInt (nAsString);
answer = findFactorial (n);
System.out.println ("Answer: " + answer);
System.exit(0);
}
public static int findFactorial (int n) This is an iterative solution to finding a factorial.
{ It’s iterative because we have a simple for loop.
int i, factorial = n;
for (i = n - 1; i >= 1; i--) Note that the for loop goes from n-1 to 1.
factorial = factorial * i;
return factorial;
}
}
Factorials
• Computing factorials are a classic problem for
examining recursion.
• A factorial is defined as follows:
n! = n * (n-1) * (n-2) …. * 1;
• For example:
1! = 1 (Base Case)
2! = 2 * 1 = 2 If you study this table closely, you
3! = 3 * 2 * 1 = 6 will start to see a pattern.
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120
Seeing the Pattern
• Seeing the pattern in the factorial example is
difficult at first.
• But, once you see the pattern, you can apply this
pattern to create a recursive solution to the
problem.
• Divide a problem up into:
– What it can do (usually a base case)
– What it cannot do
• What it cannot do resembles original problem
• The function launches a new copy of itself (recursion step) to
solve what it cannot do.
Factorials
• Computing factorials are a classic problem for
examining recursion.
• A factorial is defined as follows:
n! = n * (n-1) * (n-2) …. * 1; If you study this table closely, you
• For example: will start to see a pattern.
The pattern is as follows:
1! = 1 (Base Case) You can compute the factorial of
2! = 2 * 1 = 2 any number (n) by taking n and
3! = 3 * 2 * 1 = 6 multiplying it by the factorial of (n-1).
4! = 4 * 3 * 2 * 1 = 24
For example:
5! = 5 * 4 * 3 * 2 * 1 = 120
5! = 5 * 4!
(which translates to 5! = 5 * 24 = 120)
Recursive Solution
public class FindFactorialRecursive
{
public static void main (String args[])
{
for (int i = 1; i < 10; i++)
System.out.println ( i + "! = " + findFactorial(i));
}
public static int findFactorial (int number)
{
if ( (number == 1) || (number == 0) )
return 1;
else
Base Case.
return (number * findFactorial (number-1));
}
}
Finding the factorial of 3
fact(1)
1
fact(2) fact(2) fact(2)
2
fact(3) fact(3) fact(3) fact(3) fact(3)
6
main() main() main() main() main() main()
Time 2: Time 3: Time 4: Time 5: Time 6: Time 7:
Push: fact(3) Push: fact(2) Push: fact(1) Pop: fact(1) Pop: fact(2) Pop: fact(3)
returns 1. returns 2. returns 6.
Inside findFactorial(3): Inside findFactorial(2): Inside findFactorial(1):
if (number <= 1) return 1; if (number <= 1) return 1; if (number <= 1) return 1;
else return (3 * factorial (2)); else return (2 * factorial (1)); else return (1 * factorial (0));
27
Example Using Recursion: The Fibonacci Series
• Fibonacci series
– Each number in the series is sum of two previous numbers
• e.g., 0, 1, 1, 2, 3, 5, 8, 13, 21…
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci( n – 2 )
• fibonacci(0) and fibonacci(1) are base cases
– Golden ratio (golden mean)
2003 Prentice Hall, Inc. All rights reserved.
28
import javax.swing.JOptionPane;
public class FibonacciTest
{
public static void main (String args[])
{
long number, fibonacciValue;
String numberAsString;
numberAsString = JOptionPane.showInputDialog("What Fib value do you want?");
number = Long.parseLong( numberAsString );
fibonacciValue = fibonacci( number );
System.out.println (fibonacciValue);
System.exit (0);
// recursive declaration of method fibonacci
public static long fibonacci( long n )
{
if ( n == 0 || n == 1 )
return n;
else
return fibonacci( n - 1 ) + fibonacci( n - 2 );
} // end method fibonacci
} // end class FibonacciTest
2003 Prentice Hall, Inc. All rights reserved.
29
Recursion vs. Iteration
• Iteration
– Uses repetition structures (for, while or do…while)
– Repetition through explicitly use of repetition structure
– Terminates when loop-continuation condition fails
– Controls repetition by using a counter
• Recursion
– Uses selection structures (if, if…else or switch)
– Repetition through repeated method calls
– Terminates when base case is satisfied
– Controls repetition by dividing problem into simpler one
2003 Prentice Hall, Inc. All rights reserved.
30
Recursion vs. Iteration (cont.)
• Recursion
– More overhead than iteration
– More memory intensive than iteration
– Can also be solved iteratively
– Often can be implemented with only a few lines of code
2003 Prentice Hall, Inc. All rights reserved.
