10 2 Recursion 10 3 Recursion is a fundamental problem solving technique Intro to Programming II Involves decomposing a problem into A base case that can be solved directly A recursive step that indicates how to handle more complex Recursion cases A common recursive example is factorial Chris Brooks Department of Computer Science University of San Francisco long factorial int input if input 1 return 1 else return input factorial input 1 Department of Computer Science University of San Francisco p 1 10 4 Infinite recursion double factorial int input return input factorial input 1 Exercise Fibonacci numbers void towers int ndisks Tower startTower Tower goalTower Tower tempTower if ndisks 0 return else towers ndisks 1 startTower tempTower goalTower moveDisk startTower goalTower towers ndisks 1 tempTower goalTower startTower Department of Computer Science University of San Fra 10 6 The Fibonacci numbers are defined as follows f 0 0 f 1 1 f n f n 1 f n 2 Exercise Fibonacci numbers What is a problem with the naive way of implementing Fibonacci Can you think of a way around this The first few numbers are 0 1 1 2 3 5 8 13 21 This will eventually have a stack overflow recursive version is startlingly simple Department of Computer Science University of San Francisco p 2 10 5 A common error in recursion is forgetting the base case This can lead to infinite recursion Recursion A more interesting example is the Towers of Hanoi It s hard to write an iterative program to solve this but the How would you implement Fibonacci iteratively Write a class called Fibonacci It should have a method called getFib int n that recursively calculates the nth Fibonacci number plus a main method to test it Department of Computer Science University of San Francisco p 4 Department of Computer Science University of San Francisco p 5 Department of Computer Science University of San Fra 10 7 Recursion Traversing a Maze 10 8 Solving a maze is the sort of problem that requires trial and error Exercise Solving a maze 10 9 Change the rules so that you always try to go left then right effects then up then down When you re stuck back up and undo the last thing you did This sort of approach works well with recursion Recursion in graphics We can use recursion to easily create interesting graphical Write a Maze constructor that takes two arguments row and For example recursively tiling a surface col and generates a random maze of that size We ll represent the maze as a two dimensional array 1 clear 0 blocked Start in the upper left get to the lower right Department of Computer Science University of San Francisco p 7 10 10 Recursion in graphics Exercise Department of Computer Science University of San Francisco p 8 10 11 Fractals Department of Computer Science University of San Fra 10 12 Koch Snowflake exercise Add your own pictures to the applet We can also use recursion to draw fractals Change the color scheme of the applet Change the applet so that the recursive part of the picture is in Example Koch snowflake Change the default max and min values Rule Each line segment is replaced by a wedge with sides Change the initial triangle to have its point downward the lower right that are the same length as the replaced piece As we increase the depth it begins to look like a snowflake Department of Computer Science University of San Francisco p 10 Department of Computer Science University of San Francisco p 11 Department of Computer Science University of San Fran
View Full Document
Unlocking...