Clicker Questions - 21-Recurison
Clicker Questions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <vector>
#include <iostream>
using namespace std;
int a(int b, int c)
{
cout << b << "," << c << endl;
if (b == 1 || c == 1) return c*b;
return a(b-1,c) * a(b,c-1);
}
int main()
{
int b, c, ans;
cin >> b >> c;
ans = a(b,c);
cout << ans << endl;
return 0;
}
Suppose that the program above is compiled into the executable a.out. In questions 1 through 3, please tell me the output of that command when typed into the shell. If the output is multiple lines, simply type it on one line separated by spaces.
Question 1:
1
echo 1 6 | ./a.out | tail -n 1
Answer
It returns $1 \times 6 = 6$ instantly.Question 2:
1
echo 2 2 | ./a.out | tail -n 1
Answer
a(2,2) calls a(1,2) and (2,1) and returns their product. Both a(1,2) and a(2,1) return $2$, so the answer is $4$.
Question 3:
1
echo 2 3 | ./a.out | head -n 3
Answer
a(2,3) calls a(1,3), which returns 3, and then a(2,2). So the answer is "2,3 1,3 2,2".
Question 4: The tree drawn below repesents the recursive calls that are made when you do the following:
1
echo 3 3 | ./a.out | tail -n 1
What kind of traversal would you use on this tree to calculate what gets printed?
Answer
You calculate the answer with a postorder traversal -- only after you have the return values ofa(b-1,c) and a(b,c-1) can you calculate your return value.
Question 5: What is the output? (Use the tree)
Answer
Here's the tree filled out with the values from the postorder traversal. The answer is $144$.