Sale!

Lab 5 function and recursion

$30.00

Category:

CSC230 Lab 5

Goal: This lab includes function and recursion.
Please try your best to finish the lab in class, and submit it to CANVAS.
In this lab, please write a Lab5.cpp file. There is main function in this file. Please define
one more function in the lab.
In the lecture, we know that a recursive definition has two parts:
• Base case
• Reduction step
A good example of recursive definition is factorial:
0! = 1
�! = � ∗ � − 1 ! , �� � > 0
The corresponding recursive program can be:
int factorial(int number) {
int temp;
if(number <= 1) return 1;
temp = number * factorial(number – 1);
return temp;
}
The iteration (loop) solution can be:
int factorial(int n) {
int temp = 1;
for (int counter = 1; counter <= n; counter++)
temp = temp * counter;
return fact;
}
As you can see, the recursion and iteration perform the same task. Both of them solve a
large task one piece at a time, and combine the results. However, the emphasis of
iteration is to keep repeating until the task is “done”. While the emphasis of recursion is
to break up the large problem into smaller pieces until you can solve it, then combine the
results.
There is no clear answer to which one is better. But usually mathematicians often prefer
recursive definition; programmers often prefer iterative solutions. As a programmer,
when you define recursive functions, please keep in mind that whenever a function is
called, it will incur some overhead (prepare for the stack, switch control from one
function to another function, clean up the stack frame, etc.). If a recursive function causes
excessive function invocations, the added overhead may be overwhelming. Think about
the Fibonacci sequence as an example.
An important notation related to recursion is backtracking. “Backtracking is a general
algorithm for finding all (or some) solutions to some computational problem, notably
constraint satisfaction problems, that incrementally builds candidates to the solutions, and
abandons each partial candidate c (backtracking) as soon as it determines that c cannot be
completed to a valid solution.” —– wikipedia
A classic example of using backtracking is the eight queen puzzle, that asks for all
arrangements of eight chess queens on a standard chessboard so that no queen attacks any
other. Google Developer has very good explanation of a generalized eight queen puzzle –
N-queen Problem at https://developers.google.com/optimization/puzzles/queens . A C++
solution can be found at
https://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens.
Please take some time to read these two webpages, understand the idea of the algorithm
and the code. It is a popular interview question.
In this lab, define a global array called A with size 100. The data type of the array is int.
Design a recursive function called com(int n, int t) inside Lab5.cpp file. The return type
is void. The com(int n, int t) function prints out all strings with size t. Each char in the
string is letter between 0 and 9. That means each letter has 10 choices. The generated
string should be stored in array A. Of course, at any given time, array A can store at most
one complete string.
The first parameter of the function com() indicates which letter the function is working
on. The second parameter of the function com() indicates the length of a desired string.
The following texts are several execution examples,
jli$ ./a.out 1
0
1
2
3
4
5
6
7
8
9
jli$ ./a.out 2
00
10
20
30
40
50
60
70
80
90
01
11
21
31
41
51

In above examples, the argument of the command is the string length. The first example
prints out ten strings, the second one prints out one hundred strings (partial results
displayed).
Hints:
• If n < 1, print out the string stored in array A.
• If n >=1, uses a for loop to give different values to A[n-1], recursively call com(n1, t).
Wrap up
When you’re done, jar three files to lab5.jar
jar –cvf lab5.jar *
Submit lab5.jar to Canvas.
Make sure you logout before you leave!
If you cannot finish lab in class, please save all your files. Next time you login the
computer in the lab, you can continue work on your files. Please save them before you
logout. If you work in a Linux lab, please save the file to your machine. However, if you
are working in the Mac lab, please save the file to a CLOUD. The Mac machine will
erase everything you saved once you logout.

Reviews

There are no reviews yet.

Be the first to review “Lab 5 function and recursion”

Your email address will not be published.