By reference or by value parameter?

[Franck7070]

Hi everybody,

If I have a recursive function having a signature like this one below, I'm wondering if the recursive call will pass the entire vector or if it's just a reference to it.

My concern is about memory usage... well if it passes a huge vector that way multiple times, is it correct?

If not, what's the better way (or syntax to use) not to pass the entire vector every time?

int test(const std::vector<int>& items) {
...
    result = test(items);
...
}

Thanks
Franck

[dutch]

It just keeps passing a reference, so you're golden.
Although it's hard to see how your recursion is going to make any progress unless there's another parameter.

[MILLER XYL]

It's just a reference to it, because you use '& items' but not 'items'.(That's good, it takes a long time to copy a big vector when you use 'items')

[Ganado]

The & in the function signature means "by reference". So, no worries, you're correctly passing it by reference.

You are correct that you wouldn't want to be doing copies, but more so because that would just be wasted computation than wasted stack space, since the majority of an std::vector is on the heap anyway.

But when working recursively, you always want to be sure its never used in such a way where it's called 100s of times recursively, because that could cause a stack overflow regardless of how many parameters you're passing. As a loose rule, I prefer iteration unless the recursive solution is a magnitude more clear and easy to understand.

[dutch]

you always want to be sure its never used in such a way where it's called 100s of times recursively, because that could cause a stack overflow regardless of how many parameters you're passing

As long as you write the routine using tail recursion, and you know the compiler (or language standard) guarantees tail recursion optimization, then it only uses one stack frame (i.e., it's optimized into an iterative routine).

E.g.,

#include <iostream>
#include <vector>

// Number of stack frames equals length of vector + 1.
int sum(const std::vector<int>& v, size_t i = 0) {
    if (i == v.size()) return 0;
    return v[i] + sum(v, i + 1);
}

// Number of stack frames equals 1.
int sum_tail_recursive(const std::vector<int>& v, size_t i = 0, int subsum = 0) {
    if (i == v.size()) return subsum;
    return sum_tail_recursive(v, i + 1, subsum + v[i]);
}

int main() {
    std::vector<int> v {1, 2, 3, 4, 5};
    std::cout << sum(v) << '\n';
    std::cout << sum_tail_recursive(v) << '\n';
}

Obviously for simply summing a vector, this is ridiculous.

[JLBorges]

> what's the better way (or syntax to use) not to pass the entire vector every time?

This is the usual way: pass a pair of iterators to identify the beginning and the end of the range.
(Copying an iterator is inexpensive.)

For example:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <list>
#include <string>

// iterators: https://cal-linux.com/tutorials/STL.html
template < typename ITERATOR >
void sel_sort( ITERATOR begin, ITERATOR end )
{
    if( begin != end ) // if the range is not empty
    {
        // bring the smallest element to the front
        // https://en.cppreference.com/w/cpp/algorithm/iter_swap
        // https://en.cppreference.com/w/cpp/algorithm/min_element
        std::iter_swap( begin, std::min_element( begin, end ) ) ;
        
        // sort the elements after the the smallest one in the front 
        sel_sort( ++begin, end ) ;
    }
}

template< typename RANGE > void sel_sort( RANGE& range )
{
    // https://en.cppreference.com/w/cpp/iterator/begin
    sel_sort( std::begin(range), std::end(range) ) ;
}

template< typename RANGE > void print( const RANGE& range )
{
    // range based loop: http://www.stroustrup.com/C++11FAQ.html#for
    // auto: http://www.stroustrup.com/C++11FAQ.html#auto
    for( const auto& v : range ) std::cout << v << ' ' ;
    std::cout << '\n' ;
}

int main ()
{
    std::vector<int> a { 5, 1, 9, 3, 2, 7, 6, 8, 0, 4 } ;
    print(a) ;
    sel_sort(a) ;
    print(a) ;

    std::list<std::string> b { "def", "jkl", "abc", "mno", "ghi", "stu", "pqr" } ;
    print(b) ;
    sel_sort(b) ;
    print(b) ;
}

http://coliru.stacked-crooked.com/a/f892ebd167683ffa

[Franck7070]

Thanks a lot everybody!

@dutch: You're right, it was just for the purpose of the question so I simplified a lot. Here's a little more realistic view of what I'm doing...

@JLBorges: Is what I did below is somehow like what you mentioned?

std::tuple<int, int, int> Rec(const std::vector<int>& price, int begin, int end, int diff) {

    if (begin >= end) {
        return std::tuple<int, int, int>(begin, end, 0);
    }
    if (begin + 1 == end) {
        return std::tuple<int, int, int>(begin, end, (price[end] - price[begin]));
    }

    int center = (begin + (end - begin) / 2);
    std::tuple<int, int, int> left;
    std::tuple<int, int, int> right;

	//odd
    if (((end - begin) % 2) == 0) {
        left = Rec(price, begin, center - 1, diff);
        right = Rec(price, center, end, diff);
    }
	//even
    else {
        left = Rec(price, begin, center, diff);
        right = Rec(price, center + 1, end, diff);
    }
...

Franck

[JLBorges]

> Is what I did below is somehow like what you mentioned?

It is somewhat similar.

You identify a range by passing the vector, the position of the first item and the position of the last item.

With iterators, there is no need to pass the vector: the iterator knows what item it is 'pointing' to. The end for the iterator version is not the last item, but a fictitious 'one past the last' item.
"The iterator to the end of a container or array is defined as the element following the last valid element"
https://en.cppreference.com/w/cpp/iterator/end

[Franck7070]

OK thank you again, I'll read a bit about that.

[againtry]

Passing the iterator isn't significantly less memory intensive than passing a pointer to the vector and besides the loss of intuitive correctness, ie freedom from vague obscurity, it runs the risk of unnecessary ambiguity with other vectors of the same type, and adds equally unnecessary complexity give that the vector carries with it all the necessary information regard start, general access, size and end points.