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

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 youre 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?