Recursive even numbers in C++

Question

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’t understand why my method quant 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;
}

Answer 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’t get out of 0. You can do as many recursive steps as you want, it will always return 0, because at no time there is an addition of values.

The correction involves two things:

1. the base case is only solely when the first argument is less than the second, returning 0
2. when finding a pair in the first argument, mark as even and return 1 + recursive call result; if it is not even, return only the recursive call result

This stop 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);
}

---

Luckily, as this problem is clearly not recursive, I would prefer to solve it in o(1). In this case, the answer of only one step would be thus:

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

Explaining:

• x/2 in full operation returns exactly how many even numbers there are in the range (0, x]
• num1-1 then serves to catch the open range at the upper limit; the formula then for the quantity of pairs will apply to the range (0, num1 - 1], which in this case is identical to (0, num1) in the whole
• thus, the quantity of pairs in the range [num1, num2] is processed into the number of pairs in the range (0, num2] minus the number of pairs in the range (0, num1)
• the initial condition that returns 0 ensures that an inverted interval is not passed

  without this condition the result of contaParesO1(10,1) would be -4, which wouldn’t make much sense

• this formula only works for natural numbers other than 0

Answer 2

I I usually say recursion is abused. They do it where it is simpler to make a loop. But if it is to make recursion it has to be in functional style. Recursive functions with more than one line are usually 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;
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

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

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

What I have done is to establish what 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 at the end is that the value should be 0. In your code it is 0 in all cases, so it is 0.

But it has a condition that determines whether to add 1 or not. That in more imperative code would be a if and could not be next to the output recursion condition. Joining both was another error. This would be checking whether it is even or not:

num1 % 2 == 0

Actually in C it is common to do only:

num1 & 1

I didn’t use if because it is a little 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 a if generates, so better not to use it since the cost will be lower (if the compiler can not optimize).

Use the conditional operator to stay in a row. In functional style code the imperative style with if gets weird.