Tracing Recursion Functional #1 public int f1(int n) { if (n == 0) return 0; ret
ID: 3572648 • Letter: T
Question
Tracing Recursion
Functional #1
public int f1(int n)
{
if (n == 0)
return 0;
return 5 + f1(n-1);
}
What is f1(3) ?
What does f1 compute?
Functional #2
public int f2(int n, int a)
{
if (n == 0)
return 0;
return a + f2(n-1, a);
}
What is f2(3, 4) ?
What does f2 compute?
Functional #3
public int f3(int n, int a)
{
if (n == 0)
return 1;
return a * f3(n-1, a);
}
What is f3(x, y) ?
How many does f3 execute when called with f3(x, y) ?
Functional #4
public int f4(int n)
{
if (n == 0 || n == 1)
return 1;
return f4(n-1) + f4(n-2);
}
What is f4(5) ?
What does f4 compute?
Draw the execution tree for f4(5)?
Why is f4 so inefficient?
Functional #5
public int f5(int a, int b)
{
if (a == b)
return a;
if (a > b)
return f5(b, a - b);
else
return f5(b - a, a);
}
What is f5(30, 36) ?
What is f5(x, y) ?
Functional #6
public int f6(int a, int b)
{
if (a < b)
return f6(b, a);
if (a % b == 0)
return b;
else
return f6(a, a % b);
}
What is f6(30, 36) ?
What is f6(x, y) ?
Functional #7
public int f7(int n) { return f7h(2 * n – 1); }
public int f7h(int n)
{
if (n == 1)
return 1;
return n + f7h(n - 2);
}
What is f7(5) ?
What does f7 compute?
Explanation / Answer
Function#1
N = 3
Return 5 + f1(3-1) = return 5 +f1(2)
N = 2
Return 5 + f1(3) +f1(2)
N = 1
Return 5 + f1(3) +f1(2) + f1(1)
5 + 3 + 2 + 1 = 11
F1 compute the sum of numbers from N to 1 plus 5
Function#2
F2(3,4)
Return 4 + f2(3,4)
Return 4 + 4 + f1(2,4)
Return 4 + 4 + 4 + f1(1,4)
Return 4 + 4 + 4 + 4 = 16
This function will return the sum of 4 from 1 to n
Function#3
F3(x,y)
Return y * f3(x-1,y) and so on
This function will return the multiplication of x n times
Function#4
F4(5)
Return F4(4) + f4(3)
Return F4(4) + f4(3) + F4(2) + f4(1) = 4 + 3 + 2 + 1 = 10
This function will work as finding the sum from n-1 to 1
Function#5
F5(30,36)
Return f5(6,30)
Return f5(24,6)
Return f5(6,18)
Return f5(12,6)
Return f5(6,6)
Return 6
Function#6
F6(30,36)
Return f6(36,30)
Return f6(36,6)
Return 6
Function #f7
F7(5)
Return 5 + f7(3)
Return 5 + f7(3) + f(1)
Return 5 + f7(3) + 1 = 5 + 3 + 1 = 9
F7 computes the sum of odd numbers from n to 1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.