How do I reduce this recursive function?

Question

Hey guys,

I’ve got this function in Java:
static int func(int i){
return i<=0? 2: i+func(i%3-1)-func(i/2);

So the result is 11 but I get 9 when tried to reduce it like this:
func(13)
-> 13 + func(0) - func(6)
-> 13 + 2 - 6 + func(-1) - func(3)
-> 9 + 2 - 3 + func(-1) - func(1)
-> 8 + 2 - 1 + func(0) - func(0)
-> 9 + 2 - 2
-> 9

Could you please tell me what I did wrong?

Answer 1

HoaiNam your analysis is missing parentheses, so it has an error in subtraction. Here it is with parentheses:

     func(13)
-> 13 + func(0) - func(6)
-> 13 + 2 - (6 + func(-1) - func(3))
-> 15 - (6 + 2 - (3 + func(-1) - func(1)))
-> 15 - (8 - (3 + 2 - (1 + func(0) - func(0))))
-> 15 - (8 - (5 - (1 + 2 - 2)))
-> 15 - (8 - (5 - 1))
-> 15 - (8 - 4)
-> 15 - 4
-> 11

Answer 2

I‘m trying to reduce the expression until it reaches the condition (i<=0) which would terminate the recursive call and give back 2 as the result. One function basically calls itself and produces 2 more functions in my case, I think it‘s called tree recursion

Answer 3

Could you please tell me what are you trying to do in this code? Recursion seems a bit difficult for me to understand..

Answer 4

Brian That recursion really got me confused for over a hour right there.. And I didnt think about the parantheses.

Answer 5

This is a peculiar function! See the graphs.
https://code.sololearn.com/cSGOEvofgPUf/?ref=app