To complete this project, you are provided the following study materials. The description of each of the assignment is provided along the relevant text described in the notes on the 0 Doc
Recursion and Its Application to Enumeration Problems/0.Description.Project.Recursion.Enumeration.pdf Assignment: Recursion and Its Application to Enumeration Problems Recursion plays a crucial role in solving many real-world problems including but not limited to sorting, traversals on trees and graphs, dynamic programming, divide and conquer, backtracking, and enumeration. Specifically, enumeration problems often deal with generating all binary strings of a certain length, generating a power set, generating all the combinations (k of n), or generating all the permutations. Learning Objectives: The learning objectives for this assignment are five-fold: • To understand the nature of the recursive function calls, especially its stack memory, using the gdb debugger • To demonstrate the ability to write a recursive solution to a given problem • To demonstrate the ability to unroll the recursive call by re-writing the recursive function as an iterative function • To benchmark and compare the performance of a recursive vs. iterative solution to a given problem • To understand how to solve Enumeration problems Study Materials: To complete this 3-part assignment, you are provided the following study materials. The description of each of the assignment is provided along the relevant text described in the notes: • Recursion.Notes-and-Assignments.html: contains the description of Assignment #1 & #2 • Recursion.DebuggingExample.gdb.html: contains an example on how to examine the stack memory needed for Assignment #1 • Recursion.Enumration.Notes-and-Assignment.html: contains the study materials for solving enumeration problems along with the description of Assignment #3. • The folder codes: contains the codes that are referenced in the notes and assignments What to Submit: You are expected to submit a single zip folder that includes the solutions to each of the Assignments #1, #2, and #3 Grading Rubric: • Assignment #1: 20 points • Assignment #2: 40 points • Assignment #3: Code: 30 points • Assignment #3: Benchmarks: 10 points Recursion and Its Application to Enumeration Problems/1.Recursion.Notes-and-Assignments.html Lecture Notes: Recursion Recursion Recursion is an extremely important programming technique -- one that students seem to have trouble with early. It's a very simple concept. If a language supports recursion (and most of them do, Fortran being a notable exception), then whenever you make a procedure call, the computer stores a few things: All your arguments and local variables. Your place in the current procedure. It actually stores these things by pushing them onto a stack. Thus, whenever a procedure call returns, it knows what to do by popping off where you are and what your arguments and local variables are. This lets you do something very important. It lets you make a call to the same procedure that you are currently running. This runs a second copy of the procedure, which will restore the first copy when it returns. Let's take a simple example (in rec1.cpp): /* 1 */ void a(int i) /* 2 */ { /* 3 */ printf("In procedure a: i = %d\n", i); /* 4 */ if (i == 10) a(9); /* 5 */ } /* 6 */ /* 7 */ main() /* 8 */ { /* 9 */ a(10); /* 10 */ } You'll note, if i equals 10, then a() calls itself. Let's look at what happens when this is executed. First, we are in main(), and it calls a(10). What happens here is that the computer stores its current context (where it is, and what its local variables are) on the stack. The stack looks like: top -->[main(): line 9] Then a(10) is executed. It will print: In procedure a: i = 10 and then it will call a(9). Once again, the computer stores its current context on the stack. The stack now looks like: top -->[a(): line 4, i = 10] [main(): line 9] Then a(9) is executed. It will print: In procedure a: i = 9 Its context is: top -->[a(): line 4, i = 9] [a(): line 4, i = 10] [main(): line 9] and then it will return. When it returns, it pops where it should return off the stack -- this is in procedure a() at line 4, with i equal to 10. The stack once again looks like: top -->[main(): line 9] Now, the first thing that happens is that a(10) returns. Again, it pops where it should return off the stack -- this is in procedure main() at line 9. Of course, what happens is that main() exits, and the program ends. Thus, the output is: In procedure a: i = 10 In procedure a: i = 9 A slightly more complex example Now, look at rec2.cpp: /* 1 */ void a(int i) /* 2 */ { /* 3 */ int j; /* 4 */ /* 5 */ j = i*5; /* 6 */ printf("In procedure a: i = %d, j = %d\n", i, j); /* 7 */ if (i > 0) a(i-1); /* 8 */ printf("Later In procedure a: i = %d, j = %d\n", i, j); /* 9 */ } /* 10 */ /* 11 */ main() /* 12 */ { /* 13 */ int i; /* 14 */ /* 15 */ i = 16; /* 16 */ a(3); /* 17 */ printf("main: %d\n", i); /* 18 */ } Again, let's see what happens when it is executed. First, we're in main() which sets i to 16 and calls a(3). This pushes the current context on the stack: top -->[main(): line 16, i = 16] Now, we execute a(3). This sets j to 15, and prints out: In procedure a: i = 3, j = 15 It then calls a(2). This pushes the current context on the stack: top -->[a(): line 7, i = 3, j = 15] [main(): line 16, i = 16] And then we call a(2). This sets j to 10, and prints out: In procedure a: i = 2, j = 10 And then it calls a(1). Once again, the current context is pushed onto the stack: top -->[a(): line 7, i = 2, j = 10] [a(): line 7, i = 3, j = 15] [main(): line 16, i = 16] And then we execute a(1). This sets j to 5, and prints out: In procedure a: i = 1, j = 5 And then it calls a(0). Once again, the current context is pushed onto the stack: top -->[a(): line 7, i = 1, j = 5] [a(): line 7, i = 2, j = 10] [a(): line 7, i = 3, j = 15] [main(): line 16, i = 16] And then we execute a(0). This sets j to 0, and prints out: In procedure a: i = 0, j = 0 Since i is zero, it skips the body of the if statement, prints out: Later In procedure a: i = 0, j = 0 and returns. Now what returning does is restore the top context on the stack, which means that we are in a() at line 7 with i = 1 and j = 5. The stack is now: top -->[a(): line 7, i = 2, j = 10] [a(): line 7, i = 3, j = 15] [main(): line 16, i = 16] It prints out: Later In procedure a: i = 1, j = 5 and a(1) returns. Once again, we restore the top context on the stack, which means that we are in a() at line 7 with i = 2 and j = 10. The stack is now: top -->[a(): line 7, i = 3, j = 15] [main(): line 16, i = 16] It prints out: Later In procedure a: i = 2, j = 10 and a(2) returns. Once again, we restore the top context on the stack, which means that we are in a() at line 7 with i = 3 and j = 15. The stack is now: top -->[main(): line 16, i = 16] It prints out: Later In procedure a: i = 3, j = 15 and a(3) returns. Finally, we restore the last context on the stack, which means that we are in main() at line 16 with i = 16. The stack is now empty. It prints out: main: 16 and exits. Thus, the whole output is: UNIX> rec2 In procedure a: i = 3, j = 15 In procedure a: i = 2, j = 10 In procedure a: i = 1, j = 5 In procedure a: i = 0, j = 0 Later In procedure a: i = 0, j = 0 Later In procedure a: i = 1, j = 5 Later In procedure a: i = 2, j = 10 Later In procedure a: i = 3, j = 15 main: 16 UNIX> Using gdb to look at the stack See the RecursionDebuggingExample.gdb.html page for an example of using gdb to look at the stack while rec2.cpp is running. Infinite recursion Obviously, just like you can write a program that goes into an infinite for() loop, you can write one that goes into an infinite recursive loop, like rec3.cpp: a(int i) { printf("In procedure a: i = %d\n", i); a(i); } main() { a(10); } When you run it, it looks like an infinite loop: UNIX> rec3 In procedure a: i = 10 In procedure a: i = 10 In procedure a: i = 10 In procedure a: i = 10 .... One difference between infinite recursion and most infinite loops is that you will run out of stack space eventually with infinite