[SOLVED] Recursion for even array in C

Issue

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

Solution

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;
    }
}

Answered By – chqrlie

Answer Checked By – Candace Johnson (BugsFixing Volunteer)