c - 递归读取数组

Question

我正在学习如何将递归应用于数组。

例如，我通常以这种方式迭代读取数组:

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

我想递归地读取一个数组。我写了以下函数:

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

它可以编译，但在运行时会抛出一个段错误。这让我感到困惑，因为该函数考虑了一个应该停止它的基本情况 0。

Answer 1

你对数组索引的计算是错误的。这一行:

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

假定n 的初始 值，但与此同时，您减少 n 每次递归步。也就是说，它不应该崩溃，而只是重复写入 a 的第一个元素，因为对于 i = n - 1，n - 1 - i 始终为零。

编写这种递归的惯用方法是在 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);
        }
    }
}

并用 i 的初始值调用它，例如read_array(a, 10, 0) 用于读取 10 元素数组。

在实践中，C 中的递归是要避免的。^*

_{* 函数式语言通常可以优化递归，C 只是使用调用堆栈，开销很大。}

---

在这个例子中，编写一个纯函数的递归的理论目的在某种程度上被一个返回void的函数打败了。如果只是学习原理，函数其实应该有返回值的。例如，您可以创建一个功能性的“列表生成器”:

#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]);
    }
}