Transcript Recursion

Chapter 11
Recursion
Slides prepared by Rose Williams, Binghamton University
Recursion Versus Iteration
• Recursion is not absolutely necessary
– Any task that can be done using recursion can
also be done in a nonrecursive manner
– A nonrecursive version of a method is called an
iterative version
• An iteratively written method will typically
use loops of some sort in place of recursion
• A recursively written method can be simpler,
but will usually run slower and use more
storage than an equivalent iterative version
© 2006 Pearson Addison-Wesley. All rights reserved
11-2
Iterative version of writeVertical
© 2006 Pearson Addison-Wesley. All rights reserved
11-3
Recursive Methods that Return a Value
• Recursion is not limited to void methods
• A recursive method can return a value of any type
• An outline for a successful recursive method that
returns a value is as follows:
– One or more cases in which the value returned is
computed in terms of calls to the same method
– the arguments for the recursive calls should be intuitively
"smaller"
– One or more cases in which the value returned is
computed without the use of any recursive calls (the base
or stopping cases)
© 2006 Pearson Addison-Wesley. All rights reserved
11-4
Another Powers Method
• The method pow from the Math class
computes powers
– It takes two arguments of type double and
returns a value of type double
• The recursive method power takes two
arguments of type int and returns a value
of type int
– The definition of power is based on the
following formula:
xn is equal to xn-1 * x
© 2006 Pearson Addison-Wesley. All rights reserved
11-5
Another Powers Method
• In terms of Java, the value returned by
power(x, n) for n>0 should be the
same as
power(x, n-1) * x
• When n=0, then power(x, n)
should return 1
– This is the stopping case
© 2006 Pearson Addison-Wesley. All rights reserved
11-6
The Recursive Method power
(Part 1 of 2)
© 2006 Pearson Addison-Wesley. All rights reserved
11-7
The Recursive Method power
(Part 1 of 2)
© 2006 Pearson Addison-Wesley. All rights reserved
11-8
Evaluating the Recursive Method Call
power(2,3)
© 2006 Pearson Addison-Wesley. All rights reserved
11-9
Example 1: Factorial
•
Let us construct a recursive version of a program that evaluates the
factorial of an integer, i.e. fact(n) = n!
•
fact(0) is defined to be 1. i.e. fact(0) = 1. This is the base step.
•
For all n > 0, fact(n) = n * fact(n – 1). This is the recursive step.
•
As an example, consider the following:
•
fact(4)
= 4 * fact(3)
= 4 * (3 * fact(2))
= 4 * (3 * (2 * fact(1)))
= 4 * (3 * (2 * (1 * fact(0))))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
=4*6
= 24
© 2006 Pearson Addison-Wesley. All rights reserved
11-10
Example 1: Program
import java.util.Scanner;
public class Factorial {
public static void main(String[] args)
{
Scanner in = new Scanner (System.in);
System.out.println("Enter an integer: ");
int n = in.nextInt();
long answer = factorial(n);
System.out.println("The factorial is: " + answer);
}
public static long factorial(int number) {
if(number == 0) //base step
return 1;
else
//recursive step
return number * factorial(number - 1);
}
}
© 2006 Pearson Addison-Wesley. All rights reserved
11-11
Example 2: Fibonacci Numbers
•
Consider the following sequence of numbers: 1, 1, 2, 3, 5, 8, 13
•
Except for the first two integers, each integer is the sum of the
previous two integers.
•
This sequence is known as fibonacci (pronounced fibo – naachee)
numbers.
•
Fibonacci numbers have important applications in computer science
and mathematics.
•
A recursive solution for calculating the nth (n > 1) is as follows:
• BASE CASE:
• RECURSIVE CASE:
© 2006 Pearson Addison-Wesley. All rights reserved
fib(n) = 1 if n = 1 or 2 (n < 2)
fib(n) = fib(n – 1) + fib(n – 2)
11-12
Example 2: Program
import java.util.Scanner;
public class Fibonacci
{
public static void main(String[] args)
{
Scanner in = new Scanner (System.in);
System.out.println("Enter an integer: ");
int n = in.nextInt();
int answer = fib(n);
System.out.println("The " + n + "th fibonacci number is: " + answer);
}
public static int fib(int number)
{
if(number <= 2) //base step
return 1;
else
//recursive step
return fib(number - 1) + fib(number - 2);
}
}
© 2006 Pearson Addison-Wesley. All rights reserved
11-13