C++: recursive function for array

Question

I'm trying to write element of array in reverse order and I came across this example

template <class T>
void reverse(T arr[], int size)
{
    if (size>=2)
    {
        swap(arr[0],arr[size-1]);
        reverse(arr+1,size-2);
    }       
}

I don't get the second line - why are they subtracting the size of the array by 2? If I have 10 elements in the "swap" function by subtracting it by 1 to swap the first element with the last element then subtracting it again by 2 would give me 8 but putting that size again in the "swap" function I would get 7!! shouldn't it be 8 instead of 7?

Where do you get 7 from? If size is 10, size - 2 is 8. size - 1 doesn't modify size. — molbdnilo
– molbdnilo, Commented Jan 15, 2017 at 15:18

AlexP · Accepted Answer · 2017-01-15 14:56:02Z

2

The function works by swapping the first and last elements of the array, then recursively doing the same thing for the sub-array from [1] to [size-2], like this (the example assumes an array with 7 elements):

|0 1 2 3 4 5 6|  <-- the array as supplied to the function
 6|1 2 3 4 5|0   <-- swap [0] with [6], call recursively for 1..5
 6 5|2 3 4|1 0   <-- swap [1] with [5], call recursively for 2..4
 6 5 4|3|2 1 0   <-- swap [2] with [4], call recursively for 3..3
 6 5 4 3 2 1 0   <-- do nothing because the size is less than 2

The size decreases by 2 at each step because 2 elements were swapped and are now in the desired order.

answered Jan 15, 2017 at 14:56

AlexP

4,47019 silver badges18 bronze badges

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

Comments

Abrikot · Accepted Answer · 2017-01-15 14:57:22Z

0

I think this code is right. Let's see what is done with a 4-element array : [0,1,2,3]

First call, arr = [0,1,2,3] and size = 4. Size is more than 2, so we swap first and last elements. arr = [3,1,2,0]. Now is the reverse call with arr = [1,2,3] and size = 2. What is going to be done ? swap(arr[0] =1, arr[size-1 =2-1=1] =2]. The new array is [3,2,1,0]. The second line exclude the last element of the array, which was already done.

answered Jan 15, 2017 at 14:57

Abrikot

1,0051 gold badge10 silver badges22 bronze badges

Collectives™ on Stack Overflow

C++: recursive function for array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related