Module 8: RECURSION

Assignment 8: Recursive Functions for Stack and Queue

Purpose:

The primary focus of Chapter Six is recursion. Recursion is the term given to methods which call themselves repeatedly in order to solve complex programming problems. Although the majority of programming problems that require repeated calls to the same method can be solved efficiently with loops, certain problems require recursion. For example, suppose a programmer was working for a film company that was producing an animated film using computer-generated graphics. The programmer was charged with creating software that draws simulated trees. As with any sophisticated project, the programmer's first step is to design a simple version of the software that encapsulates its basic purpose without being too complex. In other words, the programmer will want to design a low-tech version of the software that isn't pretty but captures the basic idea. In this case, the programmer's main focus is to solve the problem of drawing trees that branch. In the early stages of development, the programmer will strive to create an image similar to the following:

So, how should the programmer create the image? Though the above image may initially appear very simple, it is not. In order to create such an image using an algorithm, the algorithm must be designed in such a way that it creates branches for the tree. In essence, each branch is like a smaller tree in itself, and each branch spawns child branches that are also like smaller trees. Basically, the tree represents a hierarchy of branches; the tree itself consists of a few branches which, in turn, consist of a few branches which, in turn, consist of a few branches, and so on... An algorithm that can handle this feat must be designed in such a way that it creates a branch, creates child branches for that branch, creates child branches for the child branches, creates child branches for the child branches for the child branches, and so on... Creating such a complex hierarchy within a loop would not only be a nightmare but would also be limited. The best that the programmer could do within a loop would be to create the tree, a few master branches, a few child branches, and a few grandchild branches, if the programmer has a lot of patience. Such an algorithm would be a confusing mess of nested loops and would produce an image similar to the one below:

A much simpler way for the programmer to create an image similar to Tree A is to use recursion. Using recursion, the programmer can simply create one method that creates several branches. As each of these branches are created, the method calls itself to create smaller branches that spawn from the parent branches. In turn, as the method is recalled, it creates several more branches and begins the cycle all over again. The programmer's only real task is to design the method in such a way that it stops calling itself after a certain point. For example, Tree A was created by a recursive method that stops calling itself as soon as the branches become so small that they are drawn as single dots on the screen. Using recursion, the programmer can design a method that is not only simpler but is also unlimited regarding the number of branches that are created; the method can continue building the hierarchy of branches, as long as desired.

So, what does recursion have to do with data structures? In the Chapter Three Assignment sheet, we discussed the stack ADT as well as the way in which method parameters are stored on a computer. Remember that, each time a method is called, memory (RAM) must be allocated to store that method's parameters as well as any variables created from within the method itself. This data is pushed onto a stack in the computer's memory which is called the "heap". Each time a recursive method calls itself, more memory must be consumed to store the new call's data. In other words, if a recursive method that consumes 12 bytes of memory calls itself 3 times, 36 bytes of memory will be pushed onto the heap. This amount of memory will continue being consumed until one of the methods returns and its allocated memory is popped off of the heap. It is for this reason that recursive problem solving is set aside as a last resort. Recursion is not memory efficient. Any problem that can be solved efficiently without using recursion should be solved without using recursion. Recursion is only necessary when either no other option exists or other options are too slow. Programmers who chose to design recursive methods should also keep in mind that computers do not have an unlimited amount of memory. Therefore, recursive methods should limit their creation of internal variables and should limit the amount of calls they make to themselves.

Goals:

Through the completion of this assignment students should gain hands-on experience with recursive problem solving. Students should understand that some programming problems can be solved more efficiently using recursion, and other problems, such as the tree example, can only be properly solved by recursion.

Files to be Submitted:

In this assignment students should create two Java classes called Recursive, RecursiveDemo. After the assignment has been completed, both files should be submitted for grading into the Dropbox for Assignment 8, which can be found in the Dropbox menu on the course web site. Students should note that only the *.java file for each class needs to be submitted; no *.class files need to be submitted into the Dropbox.

The purpose of the assignment is to practice writing methods that are recursive. We will write four methods each is worth 15 points.

a- int sum_sqr_rec(stack stk)

which will receive a stack of "int" and output the sum of the squares of the elements in the stack.

b- int plus_minus_rec(stack stk)

which will receive a stack of "int" (example: {a,b,c,d,e,f,g,h,i,j}) and output the sum of the elements in the stack as follows:

a - b + c - d + e - f + g - h + i -j

c- void prt_chars_rev_rec(stack stk)

which will receive a stack of "char" and print its elements in reverse.

d- void prt_chars_rec(queue stk) which will receive a queue of "char" and print its elements

Remember to use the stack and queue STL.

The Assignment will require you to create 2 files:

1- Recursive.java which contains the details of creating the 4 methods as specified above:

int sum_sqr_rec(stack stk), (15 points)

int plus_minus_rec(stack stk), (15 points)

void prt_chars_rev_rec(stack stk), (15 points)

void prt_chars_rec(queue stk), (15 points)

2- RecursiveDemo.java which:A- reads a string expression:

{(1+2)+[4*(2+3)]}

and store the expression in a stack and a queue.(15 points)

a- prints the corresponding expression "in reverse" using: prt_chars_rev_rec ( 5 points)

b- prints the corresponding expressing "as is" using: prt_chars_rec.( 5 points)

B- reads an array of integers: { 1, 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 }

and store them in a stack of ints.(5 points)

Then it:

C- prints the sum of the squares of the elements in the stack using int sum_sqr_rec(stack stk) and outputting the value(5 points):

385

D- prints the sum of the elements in the stack using:

int plus_minus_rec(stack stk) and outputting the value(5 points):

1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 10 = -5