Recursion

AP Computer Science A

Chris Vollmer

Recursion

• Recursion is a fundamental programming technique that can provide elegant solutions certain kinds of problems

​

• A recursive method is a method that calls itself

​

• Each call to the method sets up a new execution environment, with new parameters and new local variables

Recursive Definitions

​

• Consider the following list of numbers:

​

24, 88, 40, 37

​

• A list can be defined recursively

​

A LIST is a: number

or a: number comma LIST

​

​

• That is, a LIST is defined to be a single number, or a number followed by a comma followed by a LIST

​

• The concept of a LIST is used to define itself

​

Recursive Definitions

​

• The recursive part of the LIST definition is used several times, ultimately terminating with the non-recursive part:

​

​

number comma LIST

24 , 88, 40, 37

​

number comma LIST

88 , 40, 37

​

number comma LIST

40 , 37

​

number

37

Recursive Syntax

• All recursive definitions must have a non-recursive part

​

• If they don't, there is no way to terminate the recursive path

​

• A definition without a non-recursive part causes infinite recursion

​

• The non-recursive part is called the base case

​

Recursive Definition

public int sum(int sum)

{

int result;

if(num==1)

result=1;

else

result=num+sum(num-1);

return result;

}

Base Case or terminating condition

Move toward base case

• Will always have an if-else statement

Recursive Definition

​

• Mathematical formulas often are expressed recursively

​

• N! (N factorial), for any positive integer N, is defined to be the product of all integers between 1 and N inclusive

​

• This definition can be expressed recursively as:

​

1! = 1

N! = N * (N-1)!

​

• The concept of the factorial is defined in terms of another factorial until the base case of 1! is reached

​

Recursive Definition

public static int factorial(int n)

{

if (n==0)

return 1;

else

return n*factorial(n-1)

}

Handout3: Recursion

Tracing Recursive Method

Step 1

[3] return 1 * factorial(0)

[2] return 2 * factorial(1)

[1]return 3* factorial(2)

​

public static int factorial(int n)

{

if (n==0)

return 1;

else

return n*factorial(n-1)

}

factorial(3)

Step 2

[1] 1 * factorial(0)== 1

[2] 2 * factorial(1) 1 == 2

[3] 3* factorial(2) 2 == 6

Recursive Definition Solution (factorial)

​

​

​

5!

​

5 * 4!

​

4 * 3!

​

3 * 2!

​

2 * 1!

​

1

Recursive Programming

public int sum (int num)

{

int result;

if (num == 1)

result = 1;

else

result = num + sum (num - 1);

return result;

}

​

Method call: sum(3) - try solving

Answer on next slide

Recursive Programming Solution

result = num + sum (num - 1)

Example - Sum(3)

Video Tutorial

Practice - Handout 3: Tracing Recursion

1. public static int factorial(int n){

if(n==0)

return 1;

else

return n* factorial(n-1)

}

Factorial (5)

​

Work Down Stack...

f(5) ---- 5 * f(4)

f(4) ---- 4* f(3)

f(3) ---- 3 * f(2)

f(2) ---- 2 * f(1)

f(1) ---- 1 * f(0)

f(0) --- returns 1

n==0 terminates

​

Once loop terminates replace method call with result and work back up stack

​

f(5) ---- 5 * f(4) = 5 * 24

f(4) ---- 4* f(3) = 4 * 6

f(3) ---- 3 * f(2) = 3 * 2

f(2) ---- 2 * f(1) = 2 * 1

f(1) ---- 1 * f(0) = 1 * 1

f(0) --- returns 1

Final Answer = 120

You Do: Complete the rest of Handout 3: Tracing Recursion

We do: Example/Solution for #1

Recursion vs. Iteration

• Every recursive solution has a corresponding iterative solution
• For example, the sum (or the product) of the numbers between 1 and any positive integer N can be calculated with a for loop

​

• Recursion has the overhead of multiple method invocations

​

• Recursive solutions often are more simple and elegant than iterative solutions

Indirect Recursion

• A method invoking itself is considered to be direct recursion
• A method could invoke another method, which invokes another, etc., until eventually the original method is invoked again
• For example, method m1 could invoke m2, which invokes m3, which in turn invokes m1 again until a base case is reached
• This is called indirect recursion, and requires all the same care as direct recursion
• It is often more difficult to trace and debug

16

Indirect Recursion

17

Maze Traversal

• We can use recursion to find a path through a maze; a path can be found from any location if a path can be found from any of the location’s neighboring locations

​

• At each location we encounter, we mark the location as “visited” and we attempt to find a path from that location’s “unvisited” neighbors

​

• Recursion keeps track of the path through the maze
• The base cases are a prohibited move or arrival at the final destination

18

Maze Traversal

• See MazeSearch.java (page 473)
• See Maze.java (page 474)

​

19

Towers of Hanoi

• The Towers of Hanoi is a puzzle made up of three vertical pegs and several disks that slide on the pegs
• The disks are of varying size, initially placed on one peg with the largest disk on the bottom with increasingly smaller disks on top
• The goal is to move all of the disks from one peg to another according to the following rules:
• We can move only one disk at a time
• We cannot place a larger disk on top of a smaller disk
• All disks must be on some peg except for the disk in transit between pegs

20

Towers of Hanoi

See solution - http://towersofhanoi.info/Animate.aspx

Towers of Hanoi - Algorithm

• To move a stack of N disks from the original peg to the destination peg
• move the topmost N - 1 disks from the original peg to the extra peg
• move the largest disk from the original peg to the destination peg
• move the N-1 disks from the extra peg to the destination peg
• The base case occurs when a “stack” consists of only one disk

​

• This recursive solution is simple and elegant even though the number of move increases exponentially as the number of disks increases

​

• The iterative solution to the Towers of Hanoi is much more complex

22

Towers of Hanoi

​

• See SolveTowers.java (page 479)
• See TowersOfHanoi.java (page 480)

​

23

Recursion in Sorting

• Some sorting algorithms can be implemented recursively
• We will examine two:
• Merge sort
• Quick sort

​

... The rest of that story a little later...

​

24