Recursiveness: Compute the sum of the first positive odd values starting at 5

Asked

Viewed 920 times

3

I’m doing some exercises on and I stopped on this a few days ago.

I got to the following code: 

  /**
    * Funcao: Soma dos primeiros valores ímpares positivos começando em 5.
    * @param quantidade - quantidade de valores a somar
    *
    * valores esperados para quantidade = 1
    * 5
    * valores esperados para quantidade = 4
    * 32
    */
  public static int funcao06 (int quantidade){

    int resposta = 5;

    if(quantidade > 1){

      IO.println ("(" + quantidade + ") Valor Impar: " + (funcao06(quantidade - 1) + 2));      

    } else {

      resposta = 5;
      IO.println ("(" + quantidade + ") Valor Impar: " + resposta);

    }// fim do se

    return (resposta);

  } // fim do funcao06

Out of my job:

inserir a descrição da imagem aqui

What am I doing wrong ?!

java logic recursion

2 answers

4


I got the solution by following the following reasoning:

  • Every odd number is generated by the formula 2*n + 1;
  • The base case of the recursion is f(0) = 5 (must start from 5);

With these hypotheses we try to generalize a formula for recursion:

f(0) = 5
f(1) = 5 + 7 = 12              = f(0) + 7
f(2) = 5 + 7 + 9 = 21          = f(1) + 9
f(3) = 5 + 7 + 9 + 11 = 32     = f(2) + 11

From the above table we notice that we added a value to the result of the previous function. This value can be reached with the formula 2 * (n + 2) + 1 plus 2 in the odd number formula is on account of the start in 5.

Soon the final formula remains:

f(n) = f(n-1) + 2 * (n+2) + 1;

Turning into code we have:

public int soma(int quantidade) {
    if(quantidade == 0) {
        return 5;
    } else {
        return soma(quantidade - 1) + 2*(quantidade + 2) + 1 ;
    }
}

See on Ideone

  • 1

    I noticed that in this case when I want the sum of the first three numbers I would have to call the function in the main as follows: sum (quantity - 1); Because f(0) = 5 is the first installment of the sum!

  • It’s a matter of taste, you can change the function to start counting from 1 (instead of 0) by modifying the base case to quantity == 1, but normally in the programming we start counting from 0.

  • Yes, I left the comment as an actual observation! =)

2

Recursive solution to sum a given amount of odd numbers from an initial value:

private static int somarImpares(int valor, int quantidade) {
    assert valor % 2 != 0 : "valor: " + valor;
    assert quantidade > 0 : quantidade;

    if (quantidade > 1)
        return valor + somarImpares(valor+2,  quantidade-1);
    else
        return valor;
}

(works also for even numbers if the first assert is removed, both of them assert are mainly for documentation)

To facilitate, the following method can also be implemented

 public static int somarImparesAPartir5(int quantidade) {
    return somarImpares(5, quantidade);
}

Browser other questions tagged java logic recursion

You are not signed in. Login or sign up in order to post.