#1 - Recursion a) For each of the following problems, what is the recursive step
ID: 3727217 • Letter: #
Question
#1 - Recursion a) For each of the following problems, what is the recursive step and what is the base case? Answer in one sentence; no need to write C++ code: i) The Factorial Function, factorial (n) Recursive Step:
Base Case:
b) Traversing an SLL to find an arbitrary element, find(ptr, value) Recursive Step:
Base Case:
c) Summing N digits in an array, sum(array, index) Recursive Step:
Base Case:
b) Trace the recursion given by the following code for the data: 7 4
#include <iostream> using namespace std;
int mysteryrecursion(int a, int b) { if (0 == b) { return 0; } else { return a + mysteryrecursion(a, b-1); } }
int main() { int a = 0; int b = 0;
cin >> a >> b;
cout << mysteryrecursion(a, b) << endl; return 0;
}
Trace:
What does the code above accomplish? (If you’re not sure try different values until you see a pattern.)
Is this linear recursion? Why or why not? Is this tail recursion? Why or why not?
Explanation / Answer
i) The Factorial Function, factorial (n) Recursive Step:
The factorial function will return n*factorial (n-1) until n>1
b) Traversing an SLL to find an arbitrary element, find(ptr, value) Recursive Step:
If found then it will return the value otherwise it call the function recursively to the next ptr by prt+1 and value-1.
c) Summing N digits in an array, sum(array, index) Recursive Step:
if index < 0 then it will return the summmation. Otherwise it will return array[index] + sum(array,index-1)
d) It is not a Linear recurrsion.Linear recursion is the way where the function itself is the last statement. But in this case the function is not the last statement because it will be called until 0 == b
It is a tail recurrsion because it is mysteryrecursion(a, b-1) is not the last statement so it is decreasing the value until 0 == b.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.