c - 如果一个函数调用自己是 TRIVIALLY，它是递归的吗

Question

我被要求编写一个递归代码来打印一个数组。一位 friend 向我展示了这段代码:

include <stdio.h>
int i=0;

void print(int A[], int n)
{
    if(i<n)
    {
        printf("%d ", A[i]);
        i++;
        print(A, n);
    }
}

int main()
{
    int A[3]={3, 5, 2};
    print(A, 3);
    return 0;
}

从技术上讲，它是递归的，因为函数会调用自身，但我认为微不足道 !!它不会将问题分解为更小的问题或类似问题。所以，感觉就像是作弊。伪装成递归。

这段代码中的函数可以被认为是递归的吗？这是使用递归的好方法吗？

这种形式呢:

#include <stdio.h>

void print(int A[], int n, int i)
{
    if(i<n)
    {
        printf("%d ", A[i]);
        print(A, n, i+1);
    }
}

int main()
{
    int A[3]={3, 5, 2}, i=0;
    print(A, 3, i);
    return 0;
}

Answer 1

Can the function in this code be consider recursive?

是的，递归发生在函数可以直接或间接调用自身时。

Is this a fine way to use recursion?

没有。尽管某些编译器可能会优化代码，但代码存在引发 n 级递归并导致 stack overflow 的风险。

更好的选择是将问题减半。这在每一步都将问题分解为 2。

void print(int A[], int n, int i) {
  if (i<n) {
    A += i; n -= i;  // zero offset A and n

    int mid = n/2;
    print(A, mid, 0);              // print left side of A
    printf("%d ", A[mid]);         // print middle of A
    int right = n - mid - 1; 
    print(A + mid + 1, right, 0);  // print right side of A
  }
}

如果 n 是 1000，上面的代码可能会导致递归深度为 log2(1000) 或大约 10 而不是 1000。无界的 n 是递归可以是滥用。确保递归深度不过分。

---

请注意参数 i 并不是真正需要的。

void printA(int A[], size_t n) {
  if (n > 0) {
    size_t mid = n/2;
    printA(A, mid);              // print left side of A
    printf("%d ", A[mid]);       // print middle of A
    size_t right = n - mid - 1; 
    printA(A + mid + 1, right);  // print right side of A
  }
}