Recursion even numbers in C ++

0

The purpose of the code below is, through a recursive method, to return the number of even numbers between two numbers placed by the user. I can not understand why my quant method only returns 0.

#include <iostream>

int quant(int num1, int num2){
    int resul = 0;
    if((num1<num2) && (num1%2==0)){
        resul += quant((num1+1),num2);
        return resul;
    } else {
        return resul;
    }
}


int main(int argc, char** argv) {

    int n1,n2;

    printf("Digite o primeiro numero: ");
    scanf("%d", &n1);
    printf("Digite o segundo numero, maior que o primeiro: ");
    scanf("%d", &n2);

    int pares;
    pares = quant(n1,n2);
    printf("A quantidade de pares entre  %d %s %d %s %d",n1," e ",n2," e: ",pares);
    return 0;
}
    
asked by anonymous 27.03.2018 / 02:40

2 answers

1

I I usually say that recursion is abused . They do where it is simpler to make a tie. But if it is to do recursion it has to be in functional style. recursive functions with more than one line are often philosophically wrong, even if the result is right:

#include <stdio.h>

int quant(int num1, int num2) {
    return num1 < num2 ? quant(num1 + 1, num2) + (num1 % 2 == 0) : 0;
}

int main(int argc, char** argv) {
    int n1,n2;
    printf("Digite o primeiro numero: ");
    scanf("%d", &n1);
    printf("Digite o segundo numero, maior que o primeiro: ");
    scanf("%d", &n2);
    printf("A quantidade de pares entre %d e %d e' %d", n1, n2, quant(n1, n2));
    return 0;
}

See running on ideone . And no Coding Ground . Also I placed GitHub for future reference .

Now the function is recursive. It was difficult to see so because this is not a problem so clearly suitable for recursion.

Every recursive function must have a branch , that is, a decision that indicates when to terminate recursion, just as every loop has an exit condition. If you do not do this or enter loop infinity or give a default value if you do something that prevents infinite recursion.

What I have done is to establish which is the condition that ends the recursion and it is one:

num1 < num2

This is the condition that would end the loop and this is what I used to decide the end, and only in the end is that the value should be 0. In your code it is worth 0 in all cases, so it gives 0.

But it has a condition that determines whether to add 1 or not. This in more imperative code would be if and could not be close to the exit condition of the recursion. Joining both was another mistake. This would be the check whether it is even or not:

num1 % 2 == 0

Actually in C it's common to just do:

num1 & 1

I did not use if because it is a bit expensive and in this case it is not necessary, after all the result of this account will be 0 or 1, which is the same result as if generates, so better not to use it since the cost will be lower (if the compiler fails to optimize).

Use the conditional operator to stay on a line. In functional style code, the imperative style with if is weird.

    
27.03.2018 / 03:17
1

As I said in comment, its basic value is 0. The recursive result is 0 + return of the next recursive step. So you can not get out of 0 . You can do as many recursive steps as you want, it will always return 0, because there are no values added at any time.

Correction involves two things:

  • The base case is only only when the first argument is less than the second, returning 0
  • When you find a pair in the first argument, mark as pair and return 1 + result of the recursive call; if it is not even, return only the result of the recursive call
  • This stopping condition immediately prevents infinite recursion.

    Simply with these conditions, the code would be written like this:

    int contaParesRecursivo(int num1, int num2) {
      if (num1 > num2) {
        return 0;
      }
      int ehPar = num1 % 2 == 0? 1: 0;
      return ehPar + contaParesRecursivo(num1 + 1, num2);
    }
    

    In all fairness, since this problem is clearly non-recursive, I'd prefer to resolve it in o(1) . . In this case, the one-step response would look like this:

    int contaParesO1(int num1, int num2) {
      if (num1 > num2) {
        return 0;
      }
      return (num2/2) - ((num1 -1)/2);
    }
    

    Explaining:

    • x/2 in integer operation returns exactly how many even numbers there are in the range (0, x]
    • num1-1 in this case serves to catch make the interval open at the upper limit; then the formula for the number of pairs will then apply to the interval (0, num1 - 1] , which in this case is identical to (0, num1) in integers
    • thus, the amount of pairs in the [num1, num2] interval is transformed into the amount of pairs in the% interval with% minus the pairs in the%
    • The initial condition that returns 0 ensures that no inverted interval is passed
        

      Without this condition the result of (0, num2] would be -4, which would not make much sense

    • This formula only works for natural numbers other than 0
    27.03.2018 / 03:16