1

I am trying to write a function to print an array by recursion.

I have written three functions but they seems to be the same in terms of principle.

void printArray0( int theArray[], int theSize, int theIndex = 0 )
{
    cout << theArray[theIndex] << ' ';
    if ( ++theIndex != theSize ) printArray0( theArray, theSize, theIndex );
    else cout << endl;
}

void printArray1( int theArray[], int theElementLeft )
{
    cout << *theArray << ' ';
    if ( theElementLeft != 1 ) printArray1( theArray+1, theElementLeft-1 );
    else cout << endl;
}

void printArray2( int theArray[], int theSize )
{
    static int myIndex = 0;
    cout << theArray[myIndex] << ' ';
    if ( ++myIndex != theSize ) printArray2( theArray, theSize );
    else cout << endl;
}

So are there significant differences between them?

If there are, which function is the fastest and which is the safest?

I hope I can learn from others' experience :)

Improve this question
6
  • 1
    I never had this experience :) Commented Apr 10, 2013 at 14:21
  • Who knows what shadows lurk in the hearts of code? Only the profiler knows! Commented Apr 10, 2013 at 14:21
  • 1
    All three will fail when the given size is 0. Commented Apr 10, 2013 at 14:21
  • @JerryCoffin, a new adventure begins! Commented Apr 10, 2013 at 14:21
  • 3
    I guess the fastest and safest way is using a loop... Commented Apr 10, 2013 at 14:23

3 Answers 3

Reset to default
4

The third one is not equivalent to the first two, because it uses a static variable to keep the current state. This is a bad thing (imagine running this function from multiple threads concurrently to see why). The reason this even works is that there is never more than one recursive invocation from each invocation of a function. For example, trying to keep a static state in a recursive traversal of a binary tree would fail rather miserably. That is why the current state should be passed through parameters to your recursive functions, without using static or member context.

There should be no performance difference between the first two versions, because their time will be dominated by the output of the data.

I would change the signature of the second function like this

void printArray1( int *theArray, int theElementLeft )

because you never use theArray as an array, only as a pointer. Technically it does not matter because arrays "decay" to pointers anyway, but I think this would slightly improve readability.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

Functions 0 and 1 are equally safe1.

Function 2 is not safe in a multithreaded environment because it makes use of a static variable. Additionally, successive calls to this function will start where the last call "left off", because myIndex is never re-initialized to zero anywhere.

1Personally I would prefer the style of function 1 over function 0. Function 0 is clever in its use of pre-increment (if ( ++theIndex != theSize )) and this cleverness, in my opinion, will hamper future maintenance. A condition that has side-effects is something I would suggest that you avoid.

Improve this answer

Comments

1

Neither of them make much sense, there is no reason why anyone would ever use recursion for this. The first version is probably least bad, since it is easiest to read.

The version with static is most dangerous since it isn't thread safe. And using static makes the whole recursion (even more) pointless.

Generally, there are very few cases where recursion makes sense, this is not one of them. All three versions are dangerous, since there are no guarantees that the recursion will stop if the parameters are incorrect. All three versions will consume much more RAM memory than a plain loop and they will execute slower, while also making your program far less readable. Your program will be vulnerable to stack overflows.

Compilers typically don't optimize recursion all that efficiently. Whether they do or not may depend on whether you use "tail recursion" or not.

As a side note, your coding & indention style is unreadable and unsafe. Use a new line for each line follow an if/else and always use {} for every if/else statement.

Improve this answer

3 Comments

(As a rule of thumb, the only case where it makes sense to use recursion, is the case where it makes sense to use recursion.)
When should we use recursion? I just found that many algorithm demos used recursion so I tried to practise :(
@redcap On a more serious note, the only cases where it makes sense is when you are doing binary search, binary ("merge") sort, binary tree insert/search and similar. These are cases where recursion would likely make the algorithm more readable, and that's the only places where you should use it. Recursion can always be unrolled into a plain loop, but that loop is not necessarily more readable.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.