# WUSTL CSE 131 - sp14_6 (27 pages)

Previewing pages*1, 2, 3, 25, 26, 27*of 27 page document

**View the full content.**## sp14_6

Previewing pages *1, 2, 3, 25, 26, 27*
of
actual document.

**View the full content.**View Full Document

## sp14_6

0 0 142 views

- Pages:
- 27
- School:
- Washington University in St. Louis
- Course:
- Cse 131 - Computer Science I

**Unformatted text preview: **

Module 6 Recursion Introduction to Programming in Java An Interdisciplinary Approach Robert Sedgewick and Kevin Wayne Copyright 2002 2010 1 13 19 09 53 03 PM Overview What is recursion When one function calls itself directly or indirectly Reproductive Parts M C Escher 1948 2 Overview What is recursion When one function calls itself directly or indirectly 3 Overview What is recursion When one function calls itself directly or indirectly 4 Factorials Write a method fact N such that fact N 1 2 3 N Think recursively how does fact N relate to fact N 1 fact N fact N 1 N is it true for all N public static int fact n if n 0 return 1 else return n fact n 1 5 Substitution model for recursive evaluation public static int fact n if n 0 return 1 I tend to put base case first else return n fact n 1 fact 3 3 fact 3 1 3 fact 2 3 2 fact 2 1 3 2 fact 1 3 2 1 fact 1 1 3 2 1 fact 0 3 2 1 1 3 2 1 3 2 6 6 Greatest Common Divisor GCD Gcd Find the largest integer that evenly divides into p and q Ex gcd 4032 1272 24 4032 26 32 71 1272 23 31 531 gcd 23 31 24 7 Greatest Common Divisor Gcd Find the largest integer d that evenly divides into p and q Euclid s algorithm Euclid 300 BCE assume p q p if q 0 gcd p q gcd q p q otherwise gcd 4032 1272 gcd 1272 216 gcd 216 192 gcd 192 24 gcd 24 0 24 base case reduction step converges to base case 4032 3 1272 216 8 Greatest Common Divisor Gcd Find largest integer d that evenly divides into p and q p if q 0 gcd p q gcd q p q otherwise base case reduction step converges to base case Java implementation public static int gcd int p int q if q 0 return p else return gcd q p q base case reduction step 9 Recursive Graphics 12 Htree H tree of order n and half the size Draw an H Recursively draw 4 H trees of order n 1 one connected to each tip tip size order 1 order 2 order 3 13 Htree in Java public class Htree public static void draw int n double sz double x double y if n 0 return double x0 x sz 2 x1 x sz 2 double y0 y sz 2 y1 y sz 2 StdDraw line x0 y x1 y

View Full Document