Recursion for even array in C

user_18490551 0
Viewed 103

I understand there are a lot of questions around even recursion here, but I don't know in C wether its my logic or my syntax that's wrong (or presumably both) because from what I know I may need pointers. Especially when I'm using function in C, so I can harldy find any question that I can understand as a freshman in cs undergrads.

So my assignment was to simply create an array with even numbers in range determined in input, if input n = 10, then the array needs to contain [0, 2, 4, 6, 8, 10], if n = 9 then the array would simply be [0, 2, 4, 6, 8]. But I have to do it with recursion and I don't know what's wrong with my code since the output is somewhat weird.

#include <stdio.h>

int even(int x, int arrEven[]) {

    if (x == 0) {
        arrEven[0] = 0;
        return 0;
    }
    else if (x > 0) {    
        arrEven[x - 1] = even(x - 2, arrEven) + 1;
        return arrEven[x - 1];
    }
}

int main(void) {

    printf("n = ");
    int n;
    scanf("%d", &n);
    n = (n / 2) + 1;
    int arrEven[n];
    even(n, arrEven);

    for (int i = 0; i < (n - 1); i++) {
        printf("%d, ", arrEven[i]);
    }
    printf("%d", arrEven[n - 1]);
}

When I input 10 the output was

0, 1, -731908444, 2, 781232032, 3

instead of

0, 2, 4, 6, 8, 10
recursion function c arrays
3 Answers

You mix the usage of one variable for two purposes. In your code, n is used as index in the array and as value to be put into the array at the same time.

There are tons of options to do this. One could looke like this:

#include <stdio.h>

void even(int *arrEven, int value, int limit) {

    *arrEven = value;

    if (value < limit) {
        even(arrEven+1, value+2, limit);
    }
}

int main (void) {
    int limit;
    int count;

    printf("n = ");
    scanf("%d", &limit);
    // TODO: Check return value.
    if (limit < 0)
    {
      fprintf(stderr, "Only non-negative limits are allowed.\n");
      exit(-1);
    }

    count = (limit / 2) + 1;
    int arrEven[count];

    even(arrEven, 0, limit);

    for (int i = 0; i < count-1; i++){
        printf("%d, ", arrEven[i]);
    }
    printf("%d\n", arrEven[count-1]);
}
user_67827540

Your recursive function only initializes half the destination array because in arrEven[x - 1] = even(x - 2, arrEven) + 1; you decrement x by 2 instead of incrementing the value by 2. You can fix your code this way:

int even(int x, int arrEven[]) {

    if (x == 0) {
        arrEven[0] = 0;
        return 0;
    } else
    if (x > 0) {    
        arrEven[x - 1] = even(x - 1, arrEven) + 2;
        return arrEven[x - 1];
    }
}

Note however that the above code does not use tail recursion and will require a stack depth proportional to x. Here is an alternative where the recursion only happens just before returning from the function:

void even(int n, int arrEven[]) {
    if (n > 0) {
        errEven[n - 1] = 2 * (n - 1);
        even(n - 1, arrEven);
    }
}

The above function should compile to similar executable code as the equivalent iterative version:

void even(int n, int arrEven[]) {
    while (n > 0) {
        n = n - 1;
        errEven[n] = 2 * n;
    }
}
user_45932670

I think what you want is something like this:

int even(int x, int arrEven[])
{
    if (x == 0)
        return 0;
    arrEven[x - 1] = even(x - 1, arrEven);
    return arrEven[x - 1] + 2;
}

Here x is purely the array index, and the fact that only even values go into the array is handled by the fact that 2 is added to the value returned by even along with the terminal condition returning 0.

user_33422480
Related