Recurring Doubt

7

I did table test but the result will never give 0 because it subtracts 1 from n but then it adds the result with n . The result of this question was 36 and I did not understand why.

public class Recursivo{

    public static void main(String[] args) {

        int result = sum(8);

        System.out.println(result);
    }

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

What really does this?

return n + sum( n - 1);      
    
asked by anonymous 03.02.2016 / 17:58

2 answers

7
return n + sum( n - 1):

In this line the value of n is added to the resulting value of the sum(n-1) method.

In the example:

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


Note that sum(0) does not call the sum method again. This is the stopping point of the recursive method. When recursion finds the stopping point, just go back the whole string to go adding the values and get the return.

This will replace the values:

sum(0) = 0.
sum(1) = 1 + sum(0) = 1 + 0  = 1
sum(2) = 2 + sum(1) = 2 + 1  = 3
sum(3) = 3 + sum(2) = 3 + 3  = 6
sum(4) = 4 + sum(3) = 4 + 6 = 10
sum(5) = 5 + sum(4) = 5 + 10 = 15
sum(6) = 6 + sum(5) = 6 + 15 = 21
sum(7) = 7 + sum(6) = 7 + 21 = 28
sum(8) = 8 + sum(7) = 8 + 28 = 36

By analyzing the method sum more closely, it sums all numbers from 1 to n , in the given example: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36

    
03.02.2016 / 18:23
7
  

What really does this?

return n + sum( n - 1);    

The sum() method is always invoked by passing as a parameter the number itself received as an argument minus one, until that number reaches zero which will be when it returns zero. That is, if you pass the number 8, it will return 8 plus the return of the sum(7) method, which will return 7 plus the return of the sum(6) method, which will return 6 plus the return of the sum(5) method, which will return 5 more .... until it reaches 0, that is, every time you call the sum() method, it adds that value with all its lower values until it reaches zero.

For the case in question the return would be: 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 , that is: 36 .

To try to debug, I put prints to show what happens in each iteration:

public class Recursivo{

    public static void main(String[] args) {

        int result = sum(8);

        System.out.println("Resultado final: " + result);
    }

    public static int sum(int n){
        if( n == 0){
            System.out.println("Fim da recursividade");
            return 0;
        }
        else
        {
            System.out.println("O valor de n nessa iteração é: " + n);
            int ret =  n + sum( n - 1);
            System.out.println("O valor a ser retornado nessa iteração é: " + ret);
            return ret;
        }
    }
}

Result:

  

The value of n in this iteration is: 8
  The value of n in this iteration is: 7
  The value of n in this iteration is: 6
  The value of n in this iteration is: 5
  The value of n in this iteration is: 4
  The value of n in this iteration is: 3
  The value of n in this iteration is: 2
  The value of n in this iteration is: 1
  End of recursion
  The value to be returned in this iteration is: 1
  The value to be returned in this iteration is: 3
  The value to be returned in this iteration is: 6
  The value to be returned in this iteration is: 10
  The value to be returned in this iteration is: 15
  The value to be returned in this iteration is: 21
  The value to be returned in this iteration is: 28
  The value to be returned in this iteration is: 36
  Final score: 36

Notice that there are two prints within else in method sum() , but only the first one is shown until the end point of the recursion is reached, which is when n reaches 0 , and instead of calling the method itself it simply returns a value.

    
03.02.2016 / 18:04