need help with these questions. 1.Explain recursion and give an example in C++.
ID: 644341 • Letter: N
Question
need help with these questions.
1.Explain recursion and give an example in C++.
2.Compare a binary search and a sequential search.
3.Compare two different sorting algorithms.
4.Explain, in your own words pointers. Write a simple program to illustrate.
5.Two programs each read in numbers and find the largest. One reads input from the keyboard, the other from a file. Explain how these two programs are different and illustrate with C++ code snippets to illustrate.
6. Explain, in your own words pass by reference, write a short program to illustrate.
7.Write a short program that uses two parallel arrays. Explain the code.
8.Write a program that will use loops to generate the table shown below. The numbers are to be formatted as shown with 2 decimal places.
N N+0 N+.25 N+.5 N+.75
0 0.00 0.25 0.50 0.75
1 1.00 1.25 1.50 1.75
2 2.00 2.25 2.50 2.75
3 3.00 3.25 3.50 3.75
Explanation / Answer
Recursion
Simply put, recursion is when a function calls itself. That is, in the course of the function definition there is a call to that very same function. At first this may seem like a never ending loop, or like a dog chasing its tail. It can never catch it. So too it seems our function will never finish. This might be true is some cases, but in practice we can check to see if a certain condition is true and in that case exit (return from) our function. The case in which we end our recursion is called a base case . Additionally, just as in a loop, we must change some value and incremently advance closer to our base case.
Consider this function.
void myFunction( int counter)
{
if(counter == 0)
return;
else
{
cout <<counter<<endl;
myFunction(--counter);
return;
}
}
This recursion is not infinite, assuming the function is passed a positive integer value. What will the output be?
Consider this function:
void myFunction( int counter)
{
if(counter == 0)
return;
else
{
cout<<"hello"<<counter<<endl;
myFunction(--counter);
cout<<counter<<endl;
return;
}
}
If the function is called with the value 4, what will the output be? Explain.
The above recursion is essentially a loop like a for loop or a while loop. When do we prefer recursion to an iterative loop? We use recursion when we can see that our problem can be reduced to a simpler problem that can be solved after further reduction.
Every recursion should have the following characteristics.
The key to thinking recursively is to see the solution to the problem as a smaller version of the same problem. The key to solving recursive programming requirements is to imagine that your function does what its name says it does even before you have actually finish writing it. You must pretend the function does its job and then use it to solve the more complex cases. Here is how.
Identify the base case(s) and what the base case(s) do. A base case is the simplest possible problem (or case) your function could be passed. Return the correct value for the base case. Your recursive function will then be comprised of an if-else statement where the base case returns one value and the non-base case(s) recursively call(s) the same function with a smaller parameter or set of data. Thus you decompose your problem into two parts: (1) The simplest possible case which you can answer (and return for), and (2) all other more complex cases which you will solve by returning the result of a second calling of your function. This second calling of your function ( recursion ) will pass on the complex problem but reduced by one increment. This decomposition of the problem will actually be a complete, accurate solution for the problem for all cases other than the base case. Thus, the code of the function actually has the solution on the first recursion.
Recursion is a lot like proof by mathematical induction. That is, you show that if a statement is true for any number, n, then it must also be true for n+1. Or we could show that if the statement is true for n-1 then it must be true for n. Then you show that it is true for n=0 (or n=1). So too, in solving a a problem recursively, we write our function to work for n while we assume the function works for n-1. we then make the function work in the base case, i.e. where n=1. The key is to assume our function works when writing it. That is why we can call it from within itself. The logic is that if it works for n=1 (the base case with an explicit return), then when solving the problem for n=2 we can assume it works for n=1 because we have explicitly solved that problem. Now the solution for n=3 must also work, since we have a solution for n=2 (i.e. n = 3-1). This thinking can go on ad infinitum and therefore we have solved the problem for any n.
Let's consider writing a function to find the factorial of an integer. For example 7! equals 7*6*5*4*3*2*1 .
But we are also correct if we say 7! equals 7*6!.
In seeing the factorial of 7 in this second way we have gained a valuable insight. We now can see our problem in terms of a simpler version of our problem and we even know how to make our problem progressively more simple. We have also defined our problem in terms of itself. I.e. we defined 7! in terms of 6!. This is the essence of recursive problem solving. Now all we have left to do is decide what the base case is. What is the simplest factorial? 1!. 1! equals 1.
Let's write the factorial function recursively.
int myFactorial( int integer)
{
if( integer == 1)
return 1;
else
{
return (integer * (myFactorial(integer-1)));
}
}
Note that the base case ( the factorial of 1 ) is solved and the return value is given. Now let us imagine that our function actually works. If it works we can use it to give the result of more complex cases. If our number is 7 we will simply return 7 * the result of factorial of 6. So we actaully have the exact answer for all cases in the top level recursion. Our problem is getting smaller on each recursive call because each time we call the function we give it a smaller number. Try running this program in your head with the number 2. Does it give the right value? If it works for 1 then it must work for two since 2 merely returns 2 * factorial of 1. Now will it work for 3? Well, 3 must return 3 * factorial of 2. Now since we know that factorial of 2 works, factorial of 3 also works. We can prove that 4 works in the same way, and so on and so on.
Food for thought: ask yourself, could this be written iteratively?
Note: make it your habit of writing the base case in the function as the first statement.
2. Sequential Search
- It is easy.
- It needs not to be sorted.
- To search the last element we have element we to scan all the elements.
- If the element is first, then it
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.