Below are some quiz questions and project suggestions based on this chapter.
Quiz Questions
Below are some quiz questions.
What are the two requirements for a recursive definition?
In recursion, the case for which a solution is obtained directly is called what?
What keyword is required for a recursive subroutine?
What two keywords are required for a recursive function?
What special requirements are required of the calling routine in order to call a recursive subroutine or recursive function?
For a recursive routine, what would happen if the routine does not stop recursing?
Create a recursion tree for the recursive Fibonnaci function (as described in the following suggested projects section) with the input of 13. Note, the recursive Fibonnaci function requires two recursive calls for the non-base case step.
Suggested Projects
Below are some suggested projects.
Type in the print binary main program and recursive subroutine. Test on several data sets and verify that the program produces the correct results.
Type in the factorial main program and recursive function. Test on several data sets and verify that the program produces the correct results.
The recursive definition of Fibonnaci function is as follows:\[ fib(n) = \begin{cases} 1 & \textit{if } n =0 \\ 1 & \textit{if } n = 1 \\ fib(n-1) + fib(n-2) & \textit{if } n \geq 2 \end{cases} \nonumber \]Create a main program to read the \(n\) value from the user and ensure it is between 1 and 40. Develop recursive function, fib, to recursively compute the Fibonnaci number based on the provided definition. Note, the recursive Fibonnaci function requires two recursive calls for the non-base case step.
Develop a recursive subroutine to recursively print a star tree. Based on an initial value, \(n\), the star tree should be displayed. For example, for an \(n\) value of 5, the program should output something similar to the following:
Recursive Subroutine Program
Enter Number of Stars: 5
Star Tree:
* * * * *
* * * *
* * *
* *
*
Create a main program to read the \(n\) value from the user and ensure it is between 1 and 50. Develop recursive subroutine, printStars(), to recursively print the start tree as shown. The subroutine should print one line per call. For successive recursive calls, the \(n\) value passed as an argument should be decremented. The based case would be one (1) star.
Write a program using a recursive function to determine the number of possible paths through a two-dimensional grid. The only allowed moves are one step to the right or one step down. For example, given a grid as follows:
Moving from the starting location, (0,0) in this example, going to the end location, (3,2) in this example, can be performed in 10 different ways. Two, of the ten, different ways are shown in the example above. The function must be recursive.
Create a main program to read the initial grid coordinates and ensure that they are valid (positive values) and that the end coordinates are greater than the start coordinates. Create a recursive function, countPaths(), to determine the number of possible paths through a two- dimensional grid. The function will accept a start coordinate (row,col) and a final end coordinate (row,col).
The Tower of Hanoi is a mathematical puzzle that consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another peg, obeying the following rules:
Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.
No disk may be placed on top of a smaller disk.
The following is a recursive definition for the problem:\[ hanoi(n, \textit{from}, \textit{to}, \textit{by}) = \begin{cases} write(\text{move the disc from }\textit{from} \text{ to } \textit{to}) & \textit{if } n = 1 \\ \\ hanoi(n-1, \textit{from}, \textit{by}, \textit{to}) & \textit{if } n > 1 \\ hanoi(1, \textit{from}, \textit{to}, \textit{by}) \\ hanoi(n-1, \textit{by}, \textit{to}, \textit{from}) \end{cases} \nonumber \]Create a main program to read and validate the number of disks, \(n\), from the user and ensure it is between 1 and 10. Develop recursive function, hanoi, to recursively compute a solution to the Tower of Hanoi problem.
