week2notes.pdf

EECS 280 Discussion Notes - Week 2 Recursion and GDB Recursion is the rst major topic in computer science that many students have trouble with (the other two being pointers and dynamic memory management, which we?ll get to later in the course). In this discussion, we?ll see that recursive functions are just functions that call themselves. 1 The Call Stack First, some background: how do you describe \where the computer is" as it?s executing a program? Consider the following: #include using namespace std ; void p ri nt ( s t r i n g word ) f cout << word << endl ; cout << ? ? I printed something again ! ? ? << endl ; g void print today ( ) f s t r i n g date = "Jan 15 2008"; pr in t ( date ) ; g void p r i n t h e l l o ( ) f pr in t ( ? ? Hi ! ? ? ) ; g i n t main ( ) f print today ( ) ; p r i n t h e l l o ( ) ; p r i n t h e l l o ( ) ; g What if I say that the computer is on the second line of print()? Well, that by itself isn?t enough information. This program, when run, calls print() three times, so according to my description, we could be at any of three places in the program: called by print today() or by the rst or second call to print hello(). Therefore, the current line in the program isn?t enough; we also need to know which function called the current function (and on what line), all the way back to main(). A complete description might be: line 2 of print(), called from 1 line 1 of print_hello(), called from line 3 of main(). In reality, the computer maintains all this information using a stack of activation records containing the local variables in each function, which we?ll see in the next example. 2 Recursion Suppose I want to multiply two integers, x and y, storing the result into z, but without using the multiplication (*) operator. (Theoretical computer scientists think this sort of thing is clever.) How can I do this? Well, x times y is x added to itself y times, so we can add x y times into z (initially zero). So, in C++: // M u l t i p l i e s two numbers via addition // REQUIRES: y >= 0 // EFFECTS: returns x y i n t multiply ( i n t x , i n t y ) f i n t z = 0 ; while ( y > 0) f z += x ; y = 1 ; g return z ; g Does this work? Yes. Does it work if x = 0? y = 0? Yes and yes. What if x < 0? Yes. If y < 0? No. (Hence the REQUIRES clause.) However, there is another way to de ne multiply: multiply_r(x,y) = 0 if y == 0 = x + multiply_r(x,y-1) if y > 0 This is the recursive de nition of multiply, which we call multiply r. Recursion is the process of rerunning a function somewhere inside itself. The base case (the stopping condition) is when y == 0; multiply r(x,0) equals zero, for all values of x. The recursive step is adding x to the smaller result of multiply r. In C++, we have: // M u l t i p l i e s two numbers r e c u r s i v e l y via addition // REQUIRES: y >= 0 // EFFECTS: returns x y i n t m u l t i p l y r ( i n t x , i n t y ) f i f ( y == 0) return 0 ; return x + m u l t i p l y r (x , y 1); g How does this work? When a function is called, an activation record for its invocation is added to the top of the stack. When the function returns, its record is removed from the stack. Other functions can be 2 called from within the function, but all functions must return - destroying their activation records - in this last-in, rst-out method. So, here is what happens for multiply r(5,3): multiply_r(5,3) x=5, y=3, RA=foo multiply_r(5,2) x=5, y=2, RA=multiply_r:9 multiply_r(5,1) x=5, y=1, RA=multiply_r:9 multiply_r(5,0) x=5, y=0, RA=multiply_r:9 /* recursion stops, as hit base case */ return 0 return 5 + 0 = 5 return 5 + 5 = 10 return 5 + 10 = 15 Alternatively, here?s the call stack: +---------+ +---------+ +---------+ +---------+ | x: 5 | | x: 5 | | x: 5 | | x: 5 | | y: 3 | | y: 3 | | y: 3 | | y: 3 | +---------+ +---------+ +---------+ +---------+ multiply_r(5,3) | x: 5 | | x: 5 | | x: 5 | | y: 2 | | y: 2 | | y: 2 | +---------+ +---------+ +---------+ multiply_r(5,2) | x: 5 | | x: 5 | | y: 1 | | y: 1 | +---------+ +---------+ multiply_r(5,1) | x: 5 | | y: 0 | +---------+ (cont?d...) multiply_r(5,0) (main) reached base case ^ +---------+ +---------+ +---------+ +---------+ | | x: 5 | | x: 5 | | x: 5 | | x: 5 | return | | y: 3 | | y: 3 | | y: 3 | | y: 3 | 5+10 = 15 +---------+ +---------+ +---------+ +---------+ | x: 5 | | x: 5 | | x: 5 | ^ | y: 2 | | y: 2 | | y: 2 | | +---------+ +---------+ +---------+ return 5 + 5 = 10 | x: 5 | | x: 5 | ^ | y: 1 | | y: 1 | | +---------+ +---------+ return 0 + 5 = 5 | x: 5 | ^ | y: 0 | | +---------+ return 0 -- As an exercise, write a recursive function "power2" that will compute 2k (where k is an integer) and show the stack for power2(3). Solution: 3 // Computes the k th power of 2 r e c u r s i v e l y . // REQUIRES: k >= 0 // EFFECTS: returns 2^k i n t power2 ( i n t k ) f i f ( k == 0) return 1 ; return 2 power2 (k 1); g Stack : power2 (3) k=3, RA=foo power2 (2) k=2, RA=power2 : 9 power2 (1) k=1, RA=power2 : 9 power2 (0) k=0, RA=power2 : 9 return 1 return 2 1 = 2 return 2 2 = 4 return 2 4 = 8 With an important observation, we can cut down on the number of multiplications: p 2k p 2k = 2k (2k)1=2 (2k)1=2 = 2k 2k=2 2k=2 = 2k Since our algorithm only works on integers, if k/2 is an integer - that is, if k mod 2 == 0 - we only have to calculate (power2(k=2))2 to get power2(k) and can save some multiplications. We will call this function power2 opt: // Computes the k th power of 2 r e c u r s i v e l y , but minimizes the number of // m u l t i p l i c a t i o n s // REQUIRES: k >= 0 // EFFECTS: returns 2^k i n t power2 opt ( i n t k ) f i f ( k == 0) f return 1 ; g e l s e i f ( ( k % 2) == 0) f i n t s q r t = power2 opt ( k / 2 ) ; return s q r t s q r t ; g e l s e f return 2 power2 opt (k 1); g g This example is unlike the others as it isn?t trivial to write iteratively, but once you understand the fundamentals of recursion, the divide and conquer approach makes a lot more sense. The stack for power2(10) and power2 opt(10), being mindful of the return addresses for the latter: 4 power2(10) k=10, RA=foo power2(9) k=9, RA=power2:9 power2(8) k=8, RA=power2:9 ... power2(0) k=0, RA=power2:9 return 1 ... return 2 * 128 = 256 return 2 * 256 = 512 return 2 * 512 = 1024 power2_opt(10) k=10, RA=foo power2_opt(5) k=5, RA=power2_opt:10 power2_opt(4) k=4, RA=power2_opt:13 power2_opt(2) k=2, RA=power2_opt:10 power2_opt(1) k=1, RA=power2_opt:10 power2_opt(0) k=0, RA=power2_opt:13 return 1 return 2*power2_opt(0) = 2 return sqrt*sqrt = 4 return sqrt*sqrt = 16 return 2*power2_opt(4) = 32 return sqrt*sqrt = 1024 Notice that power2 opt performs 5 multiplications compared to power2?s 10. 3 GDB: A Quick Tour One way of debugging your code is to insert cout statements to print the values of key variables that you think might be wrong. This can become very messy very quickly, and you can forget to remove debugging code or even accidentally break your program. A better solution to this problem is to use a debugger. We?ll be covering GDB here, which is the typical tool used on Linux. The rst step in using GDB is to recompile the program (once) with debugging information, by adding -g to the compile line. (We?ll assume hello.cpp contains the print() example from earlier.) g++ -Wall -Werror -m32 hello.cpp -o hello -g Then, start GDB by typing gdb hello or, in emacs, type M-x gdb. Either way, you?ll then see a (gdb) prompt. To run your program, type \run". Ideally, it will run as normal and return to the (gdb) prompt. If it crashes (usually by a \segmentation fault" in this course), GDB will stop it where it crashed, and you?ll be able to inspect variables to see what was going on. We?ll now simulate this by setting a breakpoint. Consider the following interaction with GDB: Current directory is ~/Private/eecs280/w08/ GNU gdb Red Hat Linux (6.5-25.el5rh) Copyright (C) 2006 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. 5 This GDB was configured as "x86_64-redhat-linux-gnu"...Using host libthread_db library "/lib64/libthread_db.so.1". (gdb) break print Breakpoint 1 at 0x80488bc: file hello.cpp, line 7. (gdb) run Starting program: /afs/umich.edu/user/s/w/swolchok/Private/eecs280/w08/hello warning: Lowest section in system-supplied DSO at 0xffffe000 is .hash at ffffe0b4 Breakpoint 1, print (word=@0xffca1310) at hello.cpp:7 (gdb) bt #0 print (word=@0xffca1310) at hello.cpp:7 #1 0x08048a07 in print_today () at hello.cpp:14 #2 0x08048a72 in main () at hello.cpp:24 (gdb) print word $1 = (string &) @0xffca1310: {static npos = 4294967295, _M_dataplus = {> = {<__gnu_cxx::new_allocator> = {}, }, _M_p = 0x804a014 "Jan 15 2008"}} (gdb) continue Continuing. Jan 15 2008 I printed something again! Breakpoint 1, print (word=@0xffca130c) at hello.cpp:7 (gdb) where #0 print (word=@0xffca130c) at hello.cpp:7 #1 0x0804893d in print_hello () at hello.cpp:19 #2 0x08048a77 in main () at hello.cpp:25 (gdb) print word $2 = (string &) @0xffca130c: {static npos = 4294967295, _M_dataplus = {> = {<__gnu_cxx::new_allocator> = {}, }, _M_p = 0x804a034 "Hi!"}} (gdb) continue Continuing. Hi! I printed something again! Breakpoint 1, print (word=@0xffca130c) at hello.cpp:7 (gdb) backtrace #0 print (word=@0xffca130c) at hello.cpp:7 #1 0x0804893d in print_hello () at hello.cpp:19 #2 0x08048a7c in main () at hello.cpp:26 (gdb) info locals No locals. (gdb) print word $3 = (string &) @0xffca130c: {static npos = 4294967295, _M_dataplus = {> = {<__gnu_cxx::new_allocator> = {}, }, _M_p = 0x804a034 "Hi!"}} (gdb) up #1 0x0804893d in print_hello () at hello.cpp:19 (gdb) continue Continuing. Hi! I printed something again! 6 Program exited normally. (gdb) quit Notice that \break print" caused the program to stop whenever print() was called. A couple points to take home: \where", \bt", and \backtrace" all do the same thing { print the stack of activation records. Use whichever you like. GDB prints C++ strings a bit oddly, but the actual content of the string is next to \ M p". You can print anything while the program is stopped - try \print 2*2" or \print factorial(5)" (assuming your program has factorial in it. \up" moves one record up the call stack - if you \print x", GDB will look for x in the current record, so this lets you see what was going on in di erent functions when your program stopped. 7