CS 2110 Lecture Notes - Lecture 9: Pariah Dog, Popping

12 views7 pages
Published on 16 Mar 2017
School
Cornell University
Department
Computer Science
Course
CS 2110
Professor
Lecture 9 More Recursion
Primitive types vs Reference types
== vs equals
a== opaes a ad ’s alues
a.equals(b) compares the two objects using the equals method
Executing Recursive Methods
1. Push frame for call onto stack
2. Assign arg values to pars
3. Execute method bodies
4. Pop frame from stack and push return value on stack
Understanding Recursive Methods
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 7 pages and 3 million more documents.

1. Have a precise specification
2. Check that the method works in the base case(s).
3. Look at the recursive case(s). In your mind, replace each recursive call by
what it does according to the spec and verify correctness.
4. (No infinite recursion) Make sure that the args of recursive calls are in
some sense smaller than the pars of the method
Examples with len, dup, isPal
Efficiency with recursion
Calculating 2^n
Rathe tha 2*2*2*2…. N ties
(2*2)^n/2!!!!!!! If n is even
Recursion is a convenient and powerful way to define functions
Poles that see isuoutale a ofte e soled i a diide-and-
oue fashio:
Reduce a big problem to smaller
problems of the same kind, solve the smaller problems
Recombine the solutions to smaller
problems to form solution for big problem
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 7 pages and 3 million more documents.