Recursive and recursive methods
I am studying the final of my computer science and going back to some things that I never understood when we went through them in class. The main thing is recursion. I think I have a simple recursion example, but I am trying to work on what was in the previous exam and I am having a hard time figuring out how to do it.
Here's 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
Then we have to write a recursion function for Texas numbers, after making some adjustments after the test, this is what I came up with, I think it is correct, 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));
}
We are then asked to calculate the Tx value (5). This is where I am stuck. If the return statement for else was just n-1, I think I can figure it out, but n-1 + n-2 throws me off completely.
Can someone explain how this would work or share some links that have similar examples. I tried to find this online and in my tutorial, but the examples I found are either so advanced that I don't know what's going on, or they only deal with something like return n-1, which I already know. how to do it,
source to share
Let's start with Tx (2). n> 1, therefore 2*(Tx(n-1) + Tx(n-2))
2*(Tx(1) + Tx(0))
.
But we already know Tx (1) and Tx (0)! So just replace them and you have 2*(5 + 10) -> 30
. Great, so now we know T (2).
How about T (3)? 2*(Tx(2) + Tx(1))
... Nice, we already know that too :) Again, just fill them in to get 2*(30 + 5) -> 70
.
You can work forward to get to Tx (5).
Your code is logically correct, you should just use ==
for equality, for <assignment> =
.
When you run your method, it will work backwards and solve smaller and smaller sub-problems until it reaches the 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)
For recursion to work, whatever you do each time to break the problem down into smaller problems should make some progress in the base case. If it is not, you will keep going back endlessly until there is no free space on your computer to save all the repeated calls with 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.
source to share
You have implemented it correctly, just change = with ==.
If you want to reduce the time complexity even further, you can store the result in the global array for this function so that your function does not compute the results over and over for the same number, this will only save you 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];
}
source to share
Look, as soon as you ask the computer about the value of Tx (5), it will call the recursive function, and therefore the program will execute the else part, because the value n = 5. Now the else part will execute 2*(Tx(n-1)+Tx(n-2))
.
In the first iteration, it will become 2*((2*(Tx(3)+Tx(2)))+(2*(Tx(2)+Tx(1))))
. The iteration will continue until n is 0 or 1.
source to share