Topic 9It d ti t R iIntroduction to Recursion"T ith h"To a man with a hammer, everything looks like a nail"everything looks like a nail -Mark TwainMark Twain CS 307 Fundamentals of Computer ScienceIntroduction to Recursion1Underneath the Hood.CS 307 Fundamentals of Computer ScienceIntroduction to Recursion2The Program StackWhen you invoke a method in your code what happens when that method is completed?FooObject f = new FooObject();int x = 3;f.someFooMethod(x);f.someBarMethod(x);How does that happen? ppWhat makes it possible?CS 307 Fundamentals of Computer ScienceIntroduction to Recursion3Methods for Illustration200 bli id F M th d(i t )200 public void someFooMethod(int z)201{ int x = 2 * z;202i l()202System.out.println(x);}300 public void someBarMethod(int y) 301 {i3*301 {int x = 3 * y;302 someFooMethod(x);303 System.out.println(x);}CS 307 Fundamentals of Computer ScienceIntroduction to Recursion4The Program StackWhen your program is executed on a processor the commands are converted into another set of instructions and assigned memory locations.– normally a great deal of expansion takes place101 FooObject f = new FooObject();102 int x = 3;103 f.someFooMethod(x);104f hd()104 f.someBarMethod(x);Von Neumann ArchitectureCS 307 Fundamentals of Computer ScienceIntroduction to Recursion5Basic CPU OperationsACPU k i f t hA CPU works via a fetch command / execute command loop and a program counterloop and a program counterInstructions stored in memory (Just like data!)(Just like data!)101 FooObject f = new FooObject();jj();102 int x = 3;103 f.someFooMethod(x);104f B Mthd()104 f.someBarMethod(x);What if someFooMethod is stored at memory location 200?CS 307 Fundamentals of Computer ScienceIntroduction to Recursion6memory location 200?More on the Program Stack101 FooObject f = new FooObject();102 int x = 3;103 f.someFooMethod(x);104 f.someBarMethod(x);Line 103 is really saying go to line 200 with f as the implicit parameter and x as the explicit parameterWhen someFooMethod is done what happens?ppA. Program ends B. goes to line 103CGoes back to whatever method called itCS 307 Fundamentals of Computer ScienceIntroduction to Recursion7C.Goes back to whatever method called itActivation Records and the Program StackProgram StackWhen a method is invoked all the relevant i f ti b t th t th dinformation about the current method (variables, values of variables, next line of dtb td)i l dicode to be executed) is placed in an activation recordThe activation record is pushedonto the program stackA stack is a data structure with a single access point, the top.CS 307 Fundamentals of Computer ScienceIntroduction to Recursion8p,pThe Program StackData may either be added (pushed) or removed (popped) from a stack but it is always ftopfrom the top.– A stack of dishes– which dish do we have easy access to?CS 307 Fundamentals of Computer ScienceIntroduction to Recursion9Using RecursionUsing RecursionCS 307 Fundamentals of Computer ScienceIntroduction to Recursion10A ProblemWit th dth td t i h h i t kWrite a method that determines how much space is take up by the files in a directoryA directory can contain files and directoriesA directory can contain files and directories How many directories does our code have to examine? How would you add up the space taken up by the files in a single directory – Hint: don't worry about any sub directories at firstDirectoryandFileclassesDirectory andFile classes in the Directory class:public File[] getFiles()public Directory[] getSubdirectories() in the File classbli i t tSi ()CS 307 Fundamentals of Computer ScienceIntroduction to Recursion11public int getSize()Attendance Question 2How many levels of directories have to be visited?A. 0B.UnknownUoC. InfiniteD1D.1E. 8CS 307 Fundamentals of Computer ScienceIntroduction to Recursion12Sample Directory Structurescottmcs307APm1.txtm2.txtA.pdfhwAB.pdfa1.htm a2.htm a3.htm a4.htmCS 307 Fundamentals of Computer ScienceIntroduction to Recursion13Code for getDirectorySpace()bli i t tDi t S (Di t d)public int getDirectorySpace(Directory d){ int total = 0;File[] fileList = d.getFiles();e[] e st d.get es();for(int i = 0; i < fileList.length; i++)total += fileList[i].getSize();Directory[] dirList = d.getSubdirectories();for(int i = 0; i < dirList.length; i++)t t l + tDi t S (di Li t[i])total += getDirectorySpace(dirList[i]);return total;}}CS 307 Fundamentals of Computer ScienceIntroduction to Recursion14Attendance Question 3Is it possible to write a non recursive method to do this?A. YesB. NooCS 307 Fundamentals of Computer ScienceIntroduction to Recursion15Iterative getDirectorySpace()public int getDirectorySpace(Directory d)public int getDirectorySpace(Directory d){ ArrayList dirs = new ArrayList();File[] fileList;Directory[] dirList;ydirs.add(d);Directory temp;int total = 0;hil(!di i ())while( ! dirs.isEmpty() ){ temp = (Directory)dirs.remove(0);fileList = temp.getFiles();for(int i=0; i < fileList length; i++)for(int i 0; i < fileList.length; i++)total += fileList[i].getSize();dirList = temp.getSubdirectories();for(int i =0; i < dirList.length; i++)dirs.add( dirList[i] );}return total;}CS 307 Fundamentals of Computer ScienceIntroduction to Recursion16}Simple Recursion ExamplesSimple Recursion ExamplesCS 307 Fundamentals of Computer ScienceIntroduction to Recursion17Wisdom for Writing Recursive MethodsCS 307 Fundamentals of Computer ScienceIntroduction to Recursion18The 3 plus 1 rules of Recursion1. Know when to stop2. Decide how to take one step3. Break the journey down into that step and a smaller journeys a e jou ey4. Have faithFrom Common Lisp: A Gentle Introduction toIntroduction to Symbolic Computationby David TouretzkyCS 307 Fundamentals of Computer ScienceIntroduction to Recursion19Writing Recursive MethodsRl fR iRules of Recursion1. Base Case: Always have at least one case that can be solved without using recursioncan be solved without using recursion2. Make Progress: Any recursive call must progress toward a base case.progress toward a base case.3. "You gotta believe." Always assume that the recursive call works. (Of course you will have to design it and test it to see if it works or prove that it always works.)A recursive solution solves a small part ofA recursive solution solves a small part of the problem and leaves the rest of the problem in the same form as the originalCS 307 Fundamentals of Computer
View Full Document
Unlocking...