递归读取数组

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