Is a function recursive if it calls itself TRIVIALLY

Question

I was asked to write a recursive code to print an array. A friend showed me this code:

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

Technically, it is recursive because the function calls itself, but I think trivially !! It does not break the problem into smaller problems or anything like that. So, it felt like cheating. Faking as if it is recursion.

Can the function in this code be consider recursive? Is this a fine way to use recursion?

What about in this form:

#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?

Yes, recursion occurs when the function can call itself, either directly or indirectly.

Is this a fine way to use recursion?

No. Although some compilers may optimize the code, code risks incurring n levels of recursion and causing stack overflow

A better alternative is to halve the problem. This breaks the problem in 2 at each step.

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

If n was 1000, the above could incur a recursion depth of log2(1000) or about 10 instead of 1000. An unbounded n is a reason recursion can be abused. Insure that the recursion depth is not excessive.

---

Notice that parameter i is not really needed.

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