Read an array recursively

Question

I am learning how to apply recursion to arrays.

For example, I usually read arrays itiratively, this way:

void read_array(int *a, int n){
        int i;
        for(i = 0; i < n; ++i)
                scanf("%d", &a[i]);
        return;
}

I would like to read an array recursively. I wrote the following function:

void read_array(int *a, int n){
        int i = n - 1;
        if (n < 0)
                return;
        else{
                if(scanf("%d", &a[n - 1 - i]) == 1){
                        read_array(a, n - 1);
                        return;
                }
        }
}

It compiles, but when running it trows a segmentation fault error. It confuses me since the function contemplates a base case 0 that should stop it.

Answer 1

Your calculation of the array index is wrong. This line:

            if(scanf("%d", &a[n - 1 - i]) == 1){

assumes the initial value of n, but at the same time, you decrease n with every recursion step. That being said, it shouldn't crash but just repeatedly write the first element of a, because with i = n - 1, n - 1 - i is always zero.

The idiomatic way to write such a recursion would be to recurse on i:

void read_array(int *a, int n, int i)
{
    if (i < n)
    {
        if(scanf("%d", &a[i]) == 1)
        {
            read_array(a, n, i+1);
        }
    }
}

and call it with the initial value for i, e.g. read_array(a, 10, 0) for reading a 10-element array.

In practice, recursion in C is to be avoided.^*

_{* Functional languages can typically optimize recursion, C just uses the call stack with a lot of overhead.}

---

In this example, the theoretical purpose of recursion for writing a pure function is somewhat defeated with a function returning void. If this is just about learning the principle, the functions actually should return something. You could for example create a functional "list builder":

#include <stdio.h>
#include <stdlib.h>

// place the side effect in a separate function
int getValue(void)
{
    // could have `scanf()` here:
    return rand();
}

typedef struct List
{
    int a[10];
    size_t length;
} List;

// non-functional helper to get around limitations of C:
// (if it could initialize result directly with the new values, it would
// be functional)
List listAppend(List list, int val)
{
    List result = list;
    result.a[result.length++] = val;
    return result;
}

// recursive function without side effects:
List buildList(List list, int (*value)())
{
    if (list.length >= 10) return list;
    return buildList(listAppend(list, value()), value);
}

int main(void)
{
    List myList = buildList((List){0}, &getValue);

    for (size_t i = 0; i < myList.length; ++i)
    {
        printf("myList.a[%zu] is %d\n", i, myList.a[i]);
    }
}

Answer 2

There is a bug in the function.

As the variable i is initialized the following way

int i = n - 1;

then the second argument in this call

scanf("%d", &a[n - 1 - i])

is evaluated like

scanf("%d", &a[n - 1 - (n - 1)])

that is it is always equal to zero

scanf("%d", &a[0])

As the recursive function is called with the same value of the pointer a then all entered values are assigned to a[0]. All other elements of the array are still uninitialized.

Though this does not serve as a reason for the abnormal execution of the function.

It is possible that there is used a big array and the stack is too small to call the function recursively.

In any case the function can be defined more simply and correctly the following way

size_t read_array( int *a, size_t n )
{
    return n && scanf( "%d", a ) == 1 ? 1 + read_array( a + 1, n - 1 ) : 0;
}   

Take into account as the input can be interrupted by the user. In this case the function returns the number of initialized elements of the array.

Here is a demonstrative program.

#include <stdio.h>

size_t read_array( int *a, size_t n )
{
    return n && scanf( "%d", a ) == 1 ? 1 + read_array( a + 1, n - 1 ) : 0;
}   

#define N   10

int main(void) 
{
    int a[N];

    size_t n = read_array( a, N );

    for ( size_t i = 0; i < n; i++ ) printf( "%d ", a[i] );
    putchar( '\n' );

    return 0;
}

If to enter sequence of numbers

0 1 2 3 4 5 6 7 8 9

then the output will be

0 1 2 3 4 5 6 7 8 9

Answer 3

Example:

int read_array_aux(int *i, int *n) {
  if (i == n) {
    return 0;
  }
  if (scanf("%d", i) != 1) {
    return -1;
  }
  return read_array_aux(i + 1, n);
}

int read_array_aux2(int *a, size_t i, size_t n) {
  if (i == n) {
    return 0;
  }
  if (scanf("%d", a + i) != 1) {
    return -1;
  }
  return read_array_aux2(a, i + 1, n);
}

int read_array(int *a, size_t n) {
  return read_array_aux(a, a + n);
  // return read_array_aux2(a, 0, n);
}

Answer 4

First, condition n<0 is wrong. Probably this is the cause of segfault.

Also, why even bother about calculating the index? When processing any kind of list recursively it's worth to grasp the concept of head (first element of list) and tail (everything except head) of the list. So, filling an array recursively would be defined as (in pseudo code):

void read_array() {
   read_head();
   read_tail();
}

What is head? It's the first element of current array. What's the tail? The array starting from next element. So, read_tail is equivalent of read_array, but with the beginning moved forward by one element.

And, finally, to gather everything into one place:

void read_array(int *a, int n) {
   if(n<=0) {
       return;
   } else {
       if(scanf("%d", a) == 1) {
           read_array(a+1,n-1);
       }
   }
}

Answer 5

As other answers have mentioned, your handling of n is leading to problems. You can return 0 from the base case of sz == 0, otherwise return the result of the next recursive call, or -1 if scanf() fails. At each recursive call, increment a and decrement sz. The value returned in the calling function should be checked for input errors: 0 on success, -1 on failure.

Note that this is a tail recursion, which should be optimized by most good compilers.

#include <stdio.h>

int read_array(int *a, size_t sz);

int main(void)
{
    int arr[5];
    puts("Enter array elements:");
    if (read_array(arr, 5) != 0) {
        fprintf(stderr, "Input error\n");
    } else {
        for (size_t i = 0; i < 5; i++) {
            printf("%8d", arr[i]);
        }
        putchar('\n');
    }

    return 0;
}

int read_array(int *a, size_t sz)
{
    if (sz == 0 ) {
        return 0;
    }
    if (scanf("%d", a) == 1){
        return read_array(a + 1, sz - 1);
    } else {
        return -1;
    }
}

Sample interaction:

Enter array elements:
1 2 3 4 5
       1       2       3       4       5

Enter array elements:
1 2 3 x 5
Input error