Convert recursive method to formula
This question may be simple for you, but I don't know why I have been scratching my head since the last 2 hours.
Below is a simple code that goes through the same method 99 times and it will give 5050 as the result.
class test {
public static void main(String args[]) {
test test1 = new test();
System.out.println(test1.xyz(100));
}
public int xyz(int num) {
if(num ==1) {
return 1;
}
else {
return(xyz(num-1) + num);
}
}
}
My question is how to solve this code manually. Which equation do I need to use?
source to share
What happens in your recursive function is xyz()
summed up 100 to 1
.
100 + 99 + 98 + .... + 1
This means the addition of the first nth
natural number! Thus, you can use a simple formula to find the result:
n(n + 1) / 2
in a programme:
n = input;
sum = n(n + 1) / 2
Or, if you want a loop to find the sum, you can do this:
sum = 0;
for (i = 1; i <= input; i++)
sum += i; // sum = sum + i
source to share
The equation is actually f(n) = f(n-1) + n
and f(n)=1
for n=1
. This is actually the sum of all the numbers, but for n=100
the result is (100*101)/2 = 5050
, as the sum of positive integers: n(n+1) / 2
. The method is recursive.
If you want an iterative version, you need to use a loop for that. For example:
public static void main(String[] args) {
int result = 0;
for (int i=0; i<=100; i++) {
result = result + i;
}
System.out.println(result);
}
source to share
The first time test1.xyz(100)
it is called, it calls a method xyz()
with an argument of 100 . Then it calls return(xyz(num-1) + num);
meas, it calls xyz(99)
and adds 100 . Because it xyz(99)
is not yet evaluated, so it is pushed onto the stack. When called, xyz(99)
it calls return(xyz(num-1) + num);
meas, it calls xyz(98)
and adds to it 99
. Because it xyz(99)
is not yet evaluated, so it is pushed onto the stack. It keeps on making calls xyz()
on the stack until you call xyz(1)+2
. xyz(1)
returns 1 according to the code. Therefore, the operator xyz(1)+2
returns 3 to the call xyz(2)
. Now the compiler is issuing a call which is stackd and at the end it returns the result.
source to share
To do this, you can use the "Iterative Method" or the "Replace Method". These methods are used to calculate time complexity, but it also works for your purpose.
Basically, you write your method as a math function.
T(n) = T(n-1) + n , n > 1 T(n) = 1 , n = 1
When you do, you can iterate the function for i steps, which is a random number. For more information, you can take a look at this page:
source to share