I am trying to solve recursion by hand

Question

I am self taught and thought that I understood recursion, but I can not solve this problem:

What is returned by the call recur(12)?

What is returned by the call recur (25)?

 public static int recur (int y)
 {
      if(y <=3)
             return y%4;
      return recur(y-2) + recur(y-1) + 1;
  }

Would someone please help me with understanding how to solve these problems?

Impossible. We don't know what `y` is! Unless you mean `u`? Accuracy is pretty important.... — John3136, Jan 21 '17 at 23:18

score 0 · Answer 1 · edited May 23 '17 at 12:33

First of all, I assume you mean:

public static int recur(int y)

but the results of this method are discovered by placing a print statement at the beginning of the method:

public static int recur(int y)
  {
    System.out.println(y);
      if(y <=3)
             return y % 4;
      return recur(y-2) + recur(y-1) + 1;
  }

I am not sure what you mean by what is returned because there are several returns, though. Anyway, these are the steps to figure this out:

is 12 <= 3? No
recur(10) Don't proceed to the next recursion statement yet
is 10 <= 3? No
recur(8) Don't proceed to the next recursion statement yet
Continue this pattern until y <= 3 is true. Then you return y % 4 (whatever that number may be).
Now you are ready to go to the second recursive statement in the most recent recur() call. So, recur(y - 1).
Is y <= 3? If so, return y % 4. If not, do a process similar to step 1
once you return you add the result of recur(y - 2) + recur(y - 1) + 1. This will be a number of course.
continue this process for many iterations.

Recursion is difficult to follow and understand sometimes even for advanced programmers.

Here is a very common (and similar) problem for you to look into:

Java recursive Fibonacci sequence

I hope this helps! Good luck!

Sylwester · Answer 2 · 2017-01-22T00:11:58.597

I have removed the modulus there since any nonegative n less than 4 will just become n so I ended up with:

public static int recur (int y)
{
      return y <= 3 ?
             y :
             recur(y-2) + recur(y-1) + 1;
}

I like to start off by testing the base case so what happens for y when they are 0,1,2,3? well the argument so 0,1,2,3 of course.

What about 4? Well then it's not less or equal to 3 and you get to replace it with recur(4-2) + recur(4-1) + 1 which is recur(2) + recur(3) + 1. Now you can solve each of the recur ones since we earlier established became its argument so you end up with 2 + 3 + 1.

Now doing this for 12 or 25 is exactly the same just with more steps. Here is 5 which has just one more step:

recur(5); //=>
recur(3) + recur(4) + 1; //==>
recur(3) + ( recur(2) + recur(3) + 1 ) + 1; //==>
3 + 2 + 3 + 1 + 1; // ==>
10

So in reality the recursion halts the process in the current iteration until you have an answer that the current iteration adds together so I could have done this in the opposite way, but then I would have paused every time I now have used a previous calculated value.
You should have enough info to do any y.

score 0 · Answer 3 · answered Jan 23 '17 at 17:19

This is nothing more than an augmented Fibonacci sequence. The first four terms are defined as 0, 1, 2, 3. Thereafter, each term is the sum of the previous two terms, plus one. This +1 augmentation is where it differs from the classic Fibonacci sequence. Just add up the series by hand:

0
1
2
3
3+2+1 = 6
6+3+1 = 10
10+6+1 = 17
17+10+1 = 28
...

I am trying to solve recursion by hand

3 Answers3