3

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.

Improve this question
3
  • Have you tried drawing it on paper with small values of n? Then bigger? Commented Aug 8, 2014 at 4:46
  • That's what I'm trying to do, but that second half of the return statement keeps throwing me off. Commented Aug 8, 2014 at 4:51
  • 1
    Why? If f(n) = 2*n, what's f(3) + f(4)? Commented Aug 8, 2014 at 4:52

4 Answers 4

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Ah ok I see. Thanks! And I corrected the ==, I had had that part correct on the exam, but mistook his mark (which he drew right through the middle of one of the equals signs on both statements) and a -1 as saying that writing it as if(n==0) was wrong, but turns out he was marking them as correct and the -1 was for another error which I've since corrected.
So it would start with Tx(5), then go down to Tx(4), Tx(3), etc? Or am I still not getting it?
Yup exactly, Tx(5) = 2*(Tx(4) + Tx(3)), so then it goes and figures out Tx(4) = 2*(Tx(3) + Tx(2)) and Tx(3) = 2*(Tx(2) + Tx(1)) and so on.
3

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) ?

Improve this answer

3 Comments

Oops, I was going by the answer I got on my test, (I had it as if(n==0)) but it looked like he'd drawn a mark through one of the equals signs and wrote -1. Looking at it now I see that the mark was actually saying that part was correct and the -1 was for something else that I've since corrected. It's kind of hard to tell what he's getting at with his marks sometimes ha.
I'm not sure, part of the directions was to assume that any value entered would be positive.
@BethTanner assuming that any input number is a positive integer, then your solution (minus the correction stated above) should work!
3

You have implemented it right just change = with ==.
If you want to further reduce the time complexity you can store the result in an array global to the function so that your function doesnot compute results again and again for a same number this will only save you some time for large computations.

You can use something like this.

public int tx(int n , int []arr) {
     if (arr[n] == 0) {
          if (n == 1) {
              arr[n] = 10;
          }
          else if (n == 2) {
              arr[n] = 5;
          }
          else {
              arr[n] = 2 * (tx((n - 1), arr) + tx((n - 2), arr));
          }
      }
      return arr[n];
}
Improve this answer

Comments

2

See whenever you ask the computer for the value Tx(5) it will call the recursive function and so the program will execute the else part because value of n=5. Now in the else part 2*(Tx(n-1)+Tx(n-2)) will be executed.

In first iteration it will become 2*((2*(Tx(3)+Tx(2)))+(2*(Tx(2)+Tx(1)))) . The iteration will be continued until the value of n become 0 or 1.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.