Translate recursive method to formula

Question

This query might be simple for you guys but I don't really know why I am scratching my head from last 2 hrs.

Below is the simple code which loops through same method for 99 times and it will give 5050 as 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. What equation do I need to use?

Answer 1

What is happening in your recursive function xyz() is summing up 100 to 1.

100 + 99 + 98 + .... + 1

Which means sum up the first nth natural number! So you can use a simple formula to find the result:

n(n + 1) / 2

in program:

n = input;
sum = n(n + 1) / 2

Or, if you want to loop for finding the sum, you can do this:

sum = 0;
for (i = 1; i <= input; i++)
    sum += i; // sum = sum + i

Answer 2

The equation is actually f(n) = f(n-1) + n and f(n)=1 for n=1. This is actually sum of all the numbers and for n=100 the result is (100*101)/2 = 5050 as the sum of natural numbers is: n(n+1) / 2. The method is recursive.

If you want an iterative version then for that you need to use a loop. 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);
}