Recursion and Recursive Methods

Question

I'm studying for my computer science final and am going back over some of the things that I never quite grasped when we went over them in class. The main thing being recursion. I think I've got the hang of the simple recursion example but am trying to work through one that was on a previous exam and am having trouble figuring out how it should be done.

Here is the question:

Texas numbers (Tx(n)) are defined as follows for non-negative numbers (assume true):
Tx(n) = 10                        if n is 0
Tx(n) = 5                         if n is 1
Tx(n) = 2*(Tx(n-1) + Tx(n-2)      if n >= 2

We are then to write the recursion function for Texas numbers, after making some corrections after the test, here's what I've come up with, I think it's right, but not 100% sure.

public int Tx(int n) {
    if(n == 0)
        return 10;
    else if (n == 1)
        return 5;
    else
        return 2*(Tx(n-1) + Tx(n-2));
}

Then we are asked to computer the value of Tx(5). This is where I'm stuck. If the return statement for the else was simply n-1, I think I'd be able to figure it out, but the n-1 + n-2 is completely throwing me off.

Can anyone explain how this would work, or share some links that have similar examples. I have tried looking this up online and in my textbook but the examples I've found are either so advanced that I have no clue what's going on, or they only deal with something like return n-1, which I already know how to do.

Answer 1

Let's start with Tx(2). n > 1, so we have 2*(Tx(n-1) + Tx(n-2)) which is 2*(Tx(1) + Tx(0)).

But we already know Tx(1) and Tx(0)! So just substitute them in and you get 2*(5 + 10) -> 30. Great, so now we know T(2).

What about T(3)? 2*(Tx(2) + Tx(1)). Nice, we already know these too :) Again, just fill them in to get 2*(30 + 5) -> 70.

You can work forwards to get to Tx(5).

Your code is logically correct, you should just be using == to test equality, a single = is for assignment.

When you run your method, it will work backwards and solve smaller and smaller subproblems until it gets to a point where the answer is known, these are your base cases.

                    Tx(3)
  2*    Tx(2)         +        Tx(1)
  2*Tx(1) + Tx(0)               (5)
     (5)     (10)

In order for recursion to work, whatever you are doing each time to break the problem down into smaller problems needs to make some progress towards the base case. If it doesn't, you will just infinitely recurse until your computer runs out of space to store all of the repeated calls to the same function.

public int Tx(int n) {
    if(n == 0)
        return 10;
    else
        return Tx(n+1); // n will never reach 0!
}

Tx(1) becomes Tx(2) -> Tx(3) -> Tx(4) -> Tx(5) etc.

Answer 2

Your implementation is good, only one minor mistake - in the conditions you should replace = with == - it's not an assignment - it's a comparison.

By the way, what would you expect your method to return for Tx(-1) ?