Simple recursion help!

general
1

This gives a SIGSEGV. Any ideas?

#include <bits/stdc++.h>
using namespace std;

int getLength (string s, string::iterator it, int l) {
    if (it == s.end()) return l;
    else return getLength (s,it++,l++);
}

int main () {
    int l=0;
    string s = "hello";
    string::iterator it = s.begin();
    cout << getLength(s,it,l);
    return 0;
}
2

Hint: What is the value of the expression

it++

?

Edit:

Also - you are passing s by value - this will ensure that, even if it were incremented correctly, the expression (it == s.end()) will never be true. Why is this?

2 Likes
3

Okay so on doing string& s I’m still getting the same error. Also, on outputting the value of *it I’m getting only h repeatedly. No ideas why this is happening, though.

4

Okay it seems I need to reference it pointer. But why?

5

I’ll just post the corrected version:

#include <string>
#include <iostream>
using namespace std;

int getLength (const string& s, string::iterator it, int l) {
    if (it == s.end()) return l;
    else return getLength (s,it + 1,l + 1);
}

int main () {
    int l=0;
    string s = "hello";
    string::iterator it = s.begin();
    cout << getLength(s,it,l);
    return 0;
}

There are three errors in your code:

  1. The result of the expression it++ is simply the value of it prior to incrementing it, so you always pass the original s.begin() (from the s inside main) when you recurse i.e. the incremented it never gets seen/ checked.

(By convention in C++, the result of blah++ is always a copy of the value of blah before the increment took place, and std::string::iterator adheres to this. Again by convention, the result of ++blah is a reference to blah, which will have the newly-incremented value of blah).

  1. You passed s by copy, and checked it - which is an iterator pertaining to the original string s in main - against, essentially aCopyOfTheOriginalS.end(), and it can never equal a different string's end() :slight_smile:

That is, in theory, the following loop will never terminate:

    string s = "hello";
    string copyOfs = s;

    string::iterator it = s.begin();

    int numIncrements = 0;
    while (it != copyOfs.end())
    {   
        cout << "Incremented " << numIncrements << " times; still not reached the end!" << endl;

        it++;
        numIncrements++;
    }

although, because after it has gone past s.end() we enter the realms of Undefined Behaviour, it’s possible that in practice it does (in fact - it does on my machine, after 36 iterations with gcc, and 28 with clang XD).

  1. Similar to 1., the result of l++ is the value of l before incrementing it, so you’re essentially always passing l = 0.
9 Likes
6

That’s one hell of an explanation, @ssjgz! Thank you so much for clarifying this! :+1::+1:

1 Like
7

You’re most welcome; glad it helped :slight_smile:

5 Likes