Recursion a) For each of the following problems, what is the recursive step and

Question

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

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:

Ans: n * factorial(n-1)

Base Case:

if (n <= 1)

{

return 1;

}

b) Traversing an SLL to find an arbitrary element, find(ptr, value)

Recursive Step:

find(ptr->next, value);

Base Case:

if(ptr == NULL)

return false;

if(ptr->value == value)

return true;

c) Summing N digits in an array, sum(array, index)

Recursive Step:

array[index] + sum(array, index-1);

Base Case:

if(index == 0)

return array[index];

d)

mysteryrecursion(7, 4);

Trace: 7 + mysteryrecursion(7, 3);

mysteryrecursion(7, 3) => 7 + mysteryrecursion(7, 2)

mysteryrecursion(7, 2) => 7 + mysteryrecursion(7, 1)

mysteryrecursion(7, 1) => 7 + mysteryrecursion(7, 0)

mysteryrecursion(7, 0) => return 0

What does the code above accomplish? (If you’re not sure try different values until you see a pattern.)

Ans: mysteryrecursion() returing multiplication of a and b

Is this linear recursion? Why or why not? Is this tail recursion? Why or why not?

Yes, it is linear recursion because there is only one recursive call inside mysteryrecursion()

No, it is not tail recursion because current function’s stack frame is using

a + mysteryrecursion(a, b-1);

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.