Recursive function for an array?

[Amiplus]

Hello,

what a good recursive function that run through an entire array or vector could look like?

Assuming i have an array of words and i want to scan the array word by word, each time advancing by one word till the array end.

Thank you very much.

Kind regards

[Repeater]

This is very much something that should be done iteratively rather than recursively, but if you really like recursion, something like this would do it:

void processArrayToEnd(string* nextElementToProcess, int elementsRemaining)
{
   // process the element

   if (elementsRemaining == 0) {return;}

   processArrayToEnd(nextElementToProcess+1, elementsRemaining-1);
}

If the array is big enough, this will overflow the stack. This is exactly something where iteration is better than recursion.

[Amiplus]

Thank you.

Other way to do this?

Just to study different ways to implement

[Repeater]

With a vector:

for (auto element : the_vector)
{
  // process element
}

[icy1]

#include <iostream>
#include <vector>

using namespace std;

// Bad idea, esp if large vector...
void ShowRecursive(vector<int>::iterator it,
                  const vector<int>::iterator& end)
{
    if (it == end)
    {
        cout << '\n';
        return;
    }

    cout << *it << ' ';
    ShowRecursive(++it, end);
}


int main() 
{
    vector<int> v { 9, 7, 2, 3, 8, 4, 1 };

    // Show expected output from normal iteration
    for (auto ele : v)
        cout << ele << ' ';
    cout << '\n' << '\n';

    // Test with recursive func using built-in iterator
    ShowRecursive(v.begin(), v.end());

    return 0;
}

iterative then recursive outputs:

9 7 2 3 8 4 1 

9 7 2 3 8 4 1 

[Manga]

#include <iostream>
#include <vector>

using namespace std;

void recursion(vector<int> v, int i)
{
	cout << v[i] << " ";
	if (i < v.size() - 1) {
		recursion(v, ++i);
	}
}




int main()
{
	vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	recursion(v, 0);

	cin.get();

}

[icy1]

@Manga -- you want to change signature to avoid making extra copies of the vector and avoid a warning when comparing an unsigned size with a regular integer. Might also be clearer to put the base cases of the recursion first, but your condition is fine too.

void recursion(const vector<int>& v, unsigned i)
{
    if (i >= v.size())
        return;
    
    cout << v[i] << " ";
    recursion(v, ++i);
}

[Manga]

Solid advice icy1...

[JLBorges]

> what a good recursive function that run through an entire array or vector could look like?

In idiomatic C++, we would write such a function in terms of (polymorphic) iterators. Iterators make our code more generic; they abstract away the details of the type of sequence over which we are iterating.

Tutorial on iterators: https://cal-linux.com/tutorials/STL.html

For example:

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

template < typename ITERATOR > void print( ITERATOR begin, ITERATOR end )
{
    if( begin != end ) // if the range is not empty
    {
        std::cout << *begin << ' ' ; // print the first element
        print( ++begin, end ) ; // print the remaining elements (recursive call)
    }
    else std::cout << '\n' ; // end of sequence; print a new line (recursion 'bottoms out')
}

template < typename SEQUENCE > void print( const SEQUENCE& seq )
{
    // https://en.cppreference.com/w/cpp/iterator/begin
    print( std::begin(seq), std::end(seq) ) ;
}

int main()
{
    const int a[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
    print(a) ;

    const std::vector<std::string> b { "zero", "one", "two", "three", "four", "five" } ;
    print(b) ;

    const std::list<double> c { 0.1, 2.3, 4.5, 6.7, 8.9 } ;
    print(c) ;

    const std::string d = "abcdefghijkl" ;
    print(d) ;
}

http://coliru.stacked-crooked.com/a/3a3128b81b88d103

[Manga]

Ok JLBorges...

It looks like you have overloaded void print here. Am I correct when I say the second print function is calling the first? And the first print is recursive but not the second?

[JLBorges]

> Am I correct when I say the second print function is calling the first?
> And the first print is recursive but not the second?

Yes, and yes.

[Manga]

@JLBorges

It took me a while to figure out why you would do that, but now I get it and it seems rather clever. I got to say, your coding techniques are always brilliant but you have no ability to put things in laymen's. For years I have been reading your examples and marveling. Only lately, now that I understand how to read code better, can I fully appreciate your examples.

In idiomatic C++, we would write such a function in terms of (polymorphic) iterators.

Translation: A good practice in c++, would be to make your function a template that can be used with a variety of data types.

Idiomatic translates to native. But I think you mean it as a form of persuasion here. Polymorphic is of course a variety of types. And iterators are just a repetitive computational process.

I think Mr. Borges, once you learn to speak a couple dialects of dumbass, you will be all set to write the greatest C++ book ever!

[Amiplus]

@all


thank you very much.

Very interesting material to study.

thank you