CODEWITHSUNDEEP
javarecursion
Rei
Rei

Reputation: 512

need help to understand recursion

n = 10
10+9+8+7+6+5+4+3+2+1 = 55

here's a piece of code to add number starting from n, to every number before it.

public static int recursion(int index){
    if (index == 0){
        return 0;
    }
    else{
        return recursion(index-1) + index;
    }
}

sorry for stupid question, but here's what confuse me: when the index is not zero, it calls the recursion function again, with the index substracted by 1, so on until the index is zero. However, it's coded recursion(index-1) + index.

so why the index is not substracted by 1 and added by 10 (or any index number) each time the function is called? why is it not something like this: (10+ (9+10) + (8+10) + (7+10) +....) ?

Upvotes: 0

Views: 97

Answers (3)

Pshemo
Pshemo

Reputation: 124215

Try to write this sum as 

sum(10) = 1+2+3+4+5+6+7+8+9+10

This will let you see that 

sum(10) = (1+2+3+4+5+6+7+8+9)+10 = sum(9)+10

and 

sum(9) = (1+2+3+4+5+6+7+8)+9

and so on

In other words 

sum(i) = sum(i-1) + i;

or to be more precise 

         {0            for i=0
sum(i) = {
         {sum(i-1) + i for i>0

BTW each time method is called its variables are separate instances in each method call which means index in recursion(10) is separate variable than index in recursion(9).

Upvotes: 3

Johny
Johny

Reputation: 2188

recursion(index-1) + index;

For this statement intiallty it will be 

recursion(10-1) + index;

for evaluating that 10-1 will be done ie. 9 Then in order to find the ans of that statement recursion(9) has to be found so the function recursion is called again. so expression becomes 

recursion(9) + 10;

And recursion(9) wil be

recursion(9-1) + 9

This continues and finally it will be recursion(0) which returns 0.

Upvotes: 0

Boris the Spider
Boris the Spider

Reputation: 61148

Evaluate it by hand. Start with index = 10:

Index is not zero so we go into the else:

return recursion(10 - 1) + 10

return recursion(9) + 10

Now, recursion(9) evaluates to

return recursion(9 - 1) + 9

return recursion(8) + 9

So, substituting into the above:

return recursion(8) + 9 + 10

So, carrying on the process

return recursion(0) + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10

And we know that recursion(0) returns 0 so the recursion stops at this point.

Upvotes: 2

Related Questions