-3

I am trying to write code to recursively print out the elements of an array using an overload put operator (<<) in C++. However, I only know how to do this using non recursion. Would someone help me in translating this to do it recursively? My code is below and thanks in advance.

ostream& operator<< (ostream& outA, Recur a){

    for (int i = 0; i < a.aSize; i++){

            outA << a.aArray[i] << " ";   

    }
    outA <<  endl ;

    return outA;
}
Mary
  • 3
  • 1
  • 4

3 Answers3

0

Something like this:

ostream& operator<< (ostream& outA, Recur a) {

    if (a.size() > 0) {
        outA << a.aArray[0] << " ";
        Recur b;
        b.aArray = &a.aArray[1];
        b.setSize(a.size() - 1);
        return outA << b
    }
    else {
        outA << endl;
        return outA;
    }
}

Don't know what Recur is so I assume there is a pointer to array and a size property. The idea is to output one element and call recursively with a smaller array.

O_Z
  • 1,515
  • 9
  • 11
0

Assuming you only mean c-style arrays (where the size is part of the type definition), and not a pointer, you could roll out the following:

#include <iostream>
using namespace std;

template<typename T, size_t N>
ostream& operator<< (ostream& outA, T (& arr)[N]) {
    outA << arr[0];
    T (&next)[N-1] = reinterpret_cast<T(&)[N-1]>(arr[1]);
    outA << next;
    return outA;
}

template<typename T>
ostream& operator<< (ostream& outA, T (& arr)[1]) {
    outA << arr[0];
    return outA;
}

int main() {

    int a[] = {1, 2, 3, 4};

    cout << a;

    return 0;
}

Even though it works, it has all the overhead of recursion for a very simple task. Not to mention that ugly reinterpret_cast just so I could treat the tail of the array as an array of a smaller size... And also like NathanOliver said, you'd stamp out a separate function for each step in the recursion.

So in closing, I sincerely hope your question is purely academic.

A less awful implementation can be achieved if you use operator<< as only a wrapper that extracts the array size, and then calls the real function.

template<typename T>
void printArr(ostream& outA, T *a, size_t n) {
    if (n > 0) {
        outA << *a;
        printArr(outA, a + 1, n - 1);
    }
}

template<typename T, size_t N>
ostream& operator<< (ostream& outA, T (& arr)[N]) {
    printArr(outA, arr, N);
    return outA;
}

In this version: there only two function instantiations per invocation, there is no ugly casting, and the actual recursive call looks like a traditional recursive call.

StoryTeller - Unslander Monica
  • 165,132
  • 21
  • 377
  • 458
  • This is also going to stamp out N functions where N is the size of the array right? – NathanOliver Oct 31 '16 at 12:31
  • @NathanOliver, afraid so. Than again it [may be unrolled](https://godbolt.org/g/RzY0NY) – StoryTeller - Unslander Monica Oct 31 '16 at 12:34
  • Is that `reinterpret_cast` valid? – David G Nov 02 '16 at 03:13
  • @0x499602D2, According to [\[5.2.10/11\]](http://eel.is/c++draft/expr.reinterpret.cast#11), for lvalues, casting to a lvalue reference has the same effect as casting the address of the lvalue and dereferencing. Now, I couldn't find any explicit mention in the standard about array references decay. But since arrays will decay to pointers to the first element... I think it's valid, yet I'll retract that if proven wrong. – StoryTeller - Unslander Monica Nov 02 '16 at 06:10
-1

Here is some pseudocode:

ostream& operator<< (ostream& outA, Recur a) {
    if(a.isEmpty())
         return outA;
    outA << a.first();
    outA << a.tail();
}

It will work if you have operator<< defined for single element. a.tail() means all the elements of a without the first.

Armen Yeganyan
  • 89
  • 8
  • I belive this is infinite loop, because you never modify the array, so `!a.empty()` is always true. Remove the while and put `return` before `outA << a.tail();` to get tail recursion. – GingerPlusPlus Oct 31 '16 at 12:38