Reputation: 39
How do I trace recursive function
So in one of my class I am learning recursion and there is a question which I tried to trace through but couldn't get the right answer.
I keep geting 11 but the right answer is 6. Can someone help me get a better understanding and hopefully explain how you would trace through the code please. Thank you.
The way I tracing it right now:
int f(int x, int y) {
if (x <= 0) {
return y;
}
return f(x - 1, y + 1) - f(x / 2, y * 2);
}
What is f(4, -1)?
f(4,-1)
return f(3,0) - f(2,-2)
return f(2,1) - f(1,-4)
return f(1,2) - f(0,-8)
return f(0,3) - (-8)
return 3 + 8 = 11.
Upvotes: 3
Views: 1186
Answers (3)
Reputation: 1579
Here is ASCII art with control flow for recursive call,
f(4,-1)-------->+
. //f(4 - 1, -1 + 1)
. f(3,0)------->+
. . |
. . //f(3-1,0+1)
. . f(2,1)----------->+
. . . |
. . . // f(2-1,1+1)
. . . f(1,2)--------->+
. . . . |
. . . . //f(1-1,2+1)
. . . . f(0,3)--------->+
. . . . . //as (x == 0) return 3
. . . . . |
. . . . |<----(3)---+
. . . . |
. . . . //f(1/2,2*2)
. . . . f(0,4)--------->+
. . . . . //as (x == 0) return 4
. . . . . |
. . . . +<----(4)---+
. . . . |
. . . . //f(1-1,2+1) - f(1/2,2*2) = 3 - 4 = -1
. . . +<---(-1)---+
. . . |
. . . // f(2/2,1*2)
. . . f(1,2)--------->+
. . . . |
. . . . //f(1-1,2+1)
. . . . f(0,3)--------->+
. . . . . //as (x == 0) return 3
. . . . . |
. . . . +<----(3)---+
. . . . |
. . . . //f(1/2,2*2)
. . . . f(0,4)--------->+
. . . . . //as (x == 0) return 4
. . . . . |
. . . . +<----(4)---+
. . . . |
. . . . //f(1-1,2+1) - f(1/2,2*2) = 3 - 4 = -1
. . . +<---(-1)---+
. . +<----(0)-------+
. . |
. . //f(3/2,0*2)
. . f(1,0)----------->+
. . . |
. . . //f(1-1,0+1)
. . . f(0,1)--------->+
. . . . //as (x == 0) return 1
. . . . |
. . . +<----(1)---+
. . . |
. . . //f(1/2,0*2)
. . . f(0,0)--------->+
. . . . //as (x == 0) return 0
. . . . |
. . . +<----(0)---+
. . . |
. . . //f(0,1)-f(0,0) = 1- 0 = 0
. . +<-----(1)------+
. . |
. . // f(3-1,0+1) - f(3/2,0*) = 0 - 1 = -1
. +<----(-1)--+
. |
. //f(4/2,-1*2)
. f(2,-2)------->+
. . |
. . //f(2-1,-2+1)
. . f(1,-1)---------->+
. . . |
. . . //f(2-1,-2+1)
. . . f(0,0)--------->+
. . . . //as (x == 0) return 0
. . . . |
. . . +<----(0)---+
. . . |
. . . //f(1/2,-1*2)
. . . f(0,-2)-------->+
. . . . //as (x == 0) return -2
. . . . |
. . . +<---(-2)---+
. . . |
. . . //f(0,0)-f(0,-2) = 0 - (-2) = 2
. . +<----(2)-------+
. . |
. . //f(2/2,-2*2)
. . f(1,-4)---------->+
. . . |
. . . f(0,-3)-------->+
. . . . //as (x == 0) return -3
. . . . |
. . . +<---(-3)---+
. . . |
. . . f(0,-8)-------->+
. . . . //as (x == 0) return -8
. . . . |
. . . +<---(-8)---+
. . . |
. . . //f(0,-3) -f(0,-8) = -3 -(-8) = 5
. . +<-----(5)------+
. . |
. . //f(1,-1)-f(1,-4) = 2 - 5 = -3
. +<----(-3)--+
. |
. //f(4 - 1, -1 + 1) - f(4/2,-1*2) = -1 - (-3) = 2
<----(2)----+
How to understand,
- Each column represents a function call which makes 2 subsequent recursive calls.
<--(x)---represents return valuex
When function f(x,y) is called, recursive call for f(x-1,y+1) is called until x is zero and then f(x/2,y*2) is called recursively.
Consider below case with f(1,2) call makes two subsequent recursive call to f(0,3) and f(0,4) and return value from both is computed back as return value of f(1,2)
f(1,2)--------->+
. |
. //f(1-1,2+1)
. f(0,3)--------->+
. . //as (x == 0) return 3
. . |
. |<----(3)---+
. |
. //f(1/2,2*2)
. f(0,4)--------->+
. . //as (x == 0) return 3
. . |
. +<----(4)---+
. |
. //f(1-1,2+1) - f(1/2,2*2) = 3 - 4 = -1
+<---(-1)---+
Let me try to put it in different way,
Upvotes: 1
Reputation: 596387
You are not taking into account that most of the calls to f() are then making 2 internal calls to f(). So the real trace would break down more like the following. The real answer is 2, not 6 like your professor told you:
f(4,-1) = f(3,0) - f(2,-2)
(
f(3,0) = f(2,1) - f(1,0)
(
f(2,1) = f(1,2) - f(1,2)
(
f(1,2) = f(0,3) - f(0,4)
(
f(0,3) = 3
)
(
f(0,4) = 4
)
= (3) - (4) = -1
)
(
f(1,2) = f(0,3) - f(0,4)
(
f(0,3) = 3
)
(
f(0,4) = 4
)
= (3) - (4) = -1
)
= (-1) - (-1) = 0
)
(
f(1,0) = f(0,1) - f(0,0)
(
f(0,1) = 1
)
(
f(0,0) = 0
)
= (1) - (0) = 1
)
= (0) - (1) = -1
)
(
f(2,-2) = f(1,-1) - f(1,-4)
(
f(1,-1) = f(0,0) - f(0,-2)
(
f(0,0) = 0
)
(
f(0,-2) = -2
)
= (0) - (-2) = 2
)
(
f(1,-4) = f(0,-3) - f(0,-8)
(
f(0,-3) = -3
)
(
f(0,-8) = -8
)
= (-3) - (-8) = 5
)
= (2) - (5) = -3
)
= (-1) - (-3) = 2
final answer: 2
Upvotes: 4
Reputation: 9682
If you want, you can manually print out the traces. Probably not as good as a debugger in most cases, but it can occasionally come in handy. https://godbolt.org/z/WpSYNj
#include <iostream>
int g_tabs = 0;
struct trace
{
trace(int x, int y)
{
for(int i = 0; i < g_tabs; ++i)
std::cout << " ";
std::cout << "f(" << x << ", " << y << ") {\n";
++g_tabs;
}
~trace()
{
--g_tabs;
for(int i = 0; i < g_tabs; ++i)
std::cout << " ";
std::cout << "}\n";
}
};
void print(int res)
{
for(int i = 0; i < g_tabs; ++i)
std::cout << " ";
std::cout << "result[ " << res << " ]\n";
}
void print(int l, int r, int res)
{
for(int i = 0; i < g_tabs; ++i)
std::cout << " ";
std::cout << "result[ " << res << " ] = " << l << " - " << r << '\n';
}
int f(int x, int y)
{
trace t(x, y);
if (x <= 0) {
print(y);
return y;
}
int left = f(x - 1, y + 1);
int right = f(x / 2, y * 2);
int result = left - right;
print(left, right, result);
return result;
}
int main()
{
f(5, 3);
return 0;
}
Upvotes: 0
Related Questions
- C++ Recursive Function
- Tracing recursive function using XCode debugger
- How can I create a trace which shows the call order where there is recursion
- Tracing Recursive Function
- Recursive c++ function
- How to trace this C recursive program
- How to track a recursive function's call stack usage
- Recursive function in c++
- Tracing simple recursive function
- how to trace a recursive function C++