Please answer with C++ and comment. Only use #include <iostream> using namespace
ID: 3864689 • Letter: P
Question
Please answer with C++ and comment.
Only use
#include <iostream>
using namespace std;
Write the definition of a recursive function named find that is passed a c-string and a char and returns with the pos of the char if it finds the char within the c-string or returns -1 if the char is not found. For example, if a c-string named str containing the value "this is my string" and a char named c containing the value 'i' is passed in to find, the function should return the value 2. However, if c contained the value 'a' then find would return -1 This is what the function call for the example above would look like: int foundAt = find (str, c);Explanation / Answer
A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result and the end of each iteration. Below is an example of a recursive function.
function Count (integer N)
if (N <= 0) return "Must be a Positive Integer";
if (N > 9) return "Counting Completed";
else return Count (N+1);
end function
The function Count() above uses recursion to count from any number between 1 and 9, to the number 10. For example, Count(1) would return 2,3,4,5,6,7,8,9,10. Count(7) would return 8,9,10. The result could be used as a roundabout way to subtract the number from 10.
Recursive functions are common in computer science because they allow programmers to write efficient programs using a minimal amount of code. The downside is that they can cause infinite loops and other unexpected results if not written properly. For example, in the example above, the function is terminated if the number is 0 or less or greater than 9. If proper cases are not included in the function to stop the execution, the recursion will repeat forever, causing the program to crash, or worse yet, hang the entire computer system.
A recursive function (DEF) is a function which either calls itself or is in a potential cycle of function calls. As the definition specifies, there are two types of recursive functions. Consider a function which calls itself: we call this type of recursionimmediate recursion.
One can view this mathematically in a directed call graph.
A ---|
^ |
| |
|----|
void A() {
A();
return;
}
A() is a recursive function since it directly calls itself.
The second part of the defintion refers to a cycle (or potential cycle if we use conditional statements) which involves other functions.
Consider the following directed call graph
A ---------> B
^ |
| |
| |
|---- C <----|
This can be viewed in the following three functions:
void C() {
A();
return;
}
void B() {
C();
return;
}
void A() {
B();
return;
}
Recursive functions are an inefficient means of solving problems in terms of run times but are interesting to study nonetheless. For our purposes we will only consider immediate recursion since this will cause enough difficulty.
Fibonacci(5)
/
/
/
/
/
F(4) + F(3)
/ /
/ /
/ /
/ /
/ /
F(3) + F(2) F(2) + F(1)
/ / |
/ / |
/ / |
/ / |
F(2) + F(1) F(1) + F(0) F(1) + F(0) 1
/ | | | | |
/ | | | | |
/ | | | | |
/ | | | | |
F(1) + F(0) 1 1 0 1 0
| |
| |
| |
| |
1 0