Practicing recursion

[Fencer]

Hello, need to do some exercices that involves recursion, the
substitution model in particular (I believe that what it's called). I
decided to translate the following lisp program that sums the elements
in a list that are numbers:

(defun is-integer (x) ; Helper function to sum-only-numbers
(typep x 'integer)
)

(defun sum-only-numbers (list)
(cond
((endp list) 0)
((is-integer (first list)) (+ (first list) (sum-only-numbers(rest
list))))
(t (sum-only-numbers (rest list)))
)
)

(sum-only-numbers '(1 2 a b 33)) ; which evals to 36

I don't really know lisp and I'm interested in C++ right now, just
showing it for references.

Here's my attempt:
#include <iostream>
#include <list>
#include <sstream>
#include <string>

using namespace std;

bool is_num(const string& s)
{
istringstream iss(s);

int n;

return iss >> n;
}

int to_num(const string& s)
{
istringstream iss(s);

int n;

iss >> n;

return n;
}

int sum_only_numbers(list<string>::const_iterator itr,
list<string>::const_iterator end)
{
if (itr != end)
{
string s = *itr;

if (is_num(s))
{
return to_num(s) + sum_only_numbers(++itr, end);
}
else
{
return sum_only_numbers(++itr, end);
}
}
else
{
return 0;
}
}

int main(void)
{
string ss[] = {"1", "2", "a", "b", "33"};
list<string> l(ss, ss + sizeof(ss) / sizeof(ss[0]));

cout << sum_only_numbers(l.begin(), l.end()) << endl;
}

It prints "36" when run so it seems to work! Any helpful suggestions
before I hand it in?

- Fencer

 

[Daniel Kraft]

Hi,

Hello, need to do some exercices that involves recursion, the
substitution model in particular (I believe that what it's called). I
decided to translate the following lisp program that sums the elements
in a list that are numbers:
....

int sum_only_numbers(list<string>::const_iterator itr,
list<string>::const_iterator end)
{
if (itr != end)
{
string s = *itr;

if (is_num(s))
{
return to_num(s) + sum_only_numbers(++itr, end);

You could try to change this to a tail-recursive call, otherwise you'll
run out of stack-space pretty soon if you run the program on some large
lists.

While this is of course not that common in C++, I think g++ will be able
to optimize those calls away if you do it properly.

It would be something like this (pseudo-code):

int sum_only_numbers (iterator it, iterator end, int sum)
{
if (it == end)
return sum;

if (is_number)
return sum_only_numbers (++it, end, sum + to_number);
return sum_only_numbers (++it, end, sum);
}

and you have to call it as

sum_only_numbers (list.begin (), list.end (), 0);

}
else
{
return sum_only_numbers(++itr, end);
}
}
else
{
return 0;
}
}

int main(void)
{
string ss[] = {"1", "2", "a", "b", "33"};
list<string> l(ss, ss + sizeof(ss) / sizeof(ss[0]));

cout << sum_only_numbers(l.begin(), l.end()) << endl;
}

It prints "36" when run so it seems to work! Any helpful suggestions
before I hand it in?

- Fencer

 

[Michael DOUBEZ]

Hello, need to do some exercices that involves recursion, the
substitution model in particular (I believe that what it's called). I
decided to translate the following lisp program that sums the elements
in a list that are numbers:

(defun is-integer (x) ; Helper function to sum-only-numbers
(typep x 'integer)
)

(defun sum-only-numbers (list)
(cond
((endp list) 0)
((is-integer (first list)) (+ (first list) (sum-only-numbers(rest
list))))
(t (sum-only-numbers (rest list)))
)
)

(sum-only-numbers '(1 2 a b 33)) ; which evals to 36

I don't really know lisp and I'm interested in C++ right now, just
showing it for references.

Here's my attempt:
#include <iostream>
#include <list>
#include <sstream>
#include <string>

using namespace std;

bool is_num(const string& s)
{
istringstream iss(s);

int n;

return iss >> n;
}

int to_num(const string& s)
{
istringstream iss(s);

int n;

iss >> n;

return n;
}

The is_num and to_num could be merged into the faillible class idiom:

template<class T>
struct faillible
{
T value;
bool success;
faillible(const T& v, bool s=false) : value(v), success(s) { }
};

faillible<int> to_num(const string& s)
{
faillible<int> result(0);
//...
result.success=(iss>>result.value);
return result;
}

int sum_only_numbers(list<string>::const_iterator itr,
list<string>::const_iterator end)
{
if (itr != end)
{

const faillible<int> num_conversion=to_num(*itr);
if(num_conversion.success)
{
return num_conversion.value + sum_only_numbers(++itr, end);
}
else
{
return sum_only_numbers(++itr, end);
}

else
{
return 0;
}
}

int main(void)
{
string ss[] = {"1", "2", "a", "b", "33"};
list<string> l(ss, ss + sizeof(ss) / sizeof(ss[0]));

cout << sum_only_numbers(l.begin(), l.end()) << endl;
}

It prints "36" when run so it seems to work! Any helpful suggestions
before I hand it in?

 

[James Kanze]

Except that using recursion for this in C++ is what I would
consider bad programming practice. In a very real sense, too,
you don't have the necessary data structures to do this in
standard C++. You can emulate them for the times it's needed
(or just use boost::any), but normally, C++ is based on static
type checking, not dynamic. And while you can use std::string,
it's not really appropriate; you cannot, for example,
distiguish between a string containing "123" and the number 123,
for example.

[...]

The is_num and to_num could be merged into the faillible class
idiom:

If they're just for this one program, it's sufficient that
to_num return 0 if the value isn't a number.

template<class T>
struct faillible
{
T value;
bool success;
faillible(const T& v, bool s=false) : value(v), success(s) { }
};

And that's not really the fallible idiom. Almost by definition:

-- Fallible has two constructors, a default constructor, and
one which takes a value. You don't pass the constructor a
value you don't have, and if you pass the constructor a
value, it's because you've got one.

-- Normally, fallible will either abort or throw an exception
if you attempt to use the value, and it doesn't have one.
This means a member function for access (and usually,
support for implicit conversion), and normally, a second,
"isValid()" function, which returns the status.

Beyond that, there are a lot of bells and whistles which can be
added---Barton and Nackman had an "elseDefaultTo" function
already.

But again, *if* to_num is just for this program, Fallible is
overkill---just have it return 0 if there isn't a number.

 

[James Kanze]

You could try to change this to a tail-recursive call,
otherwise you'll run out of stack-space pretty soon if you run
the program on some large lists.

While this is of course not that common in C++, I think g++
will be able to optimize those calls away if you do it
properly.

It would be something like this (pseudo-code):

int sum_only_numbers (iterator it, iterator end, int sum)
{
if (it == end)
return sum;

if (is_number)
return sum_only_numbers (++it, end, sum + to_number);
return sum_only_numbers (++it, end, sum);
}

If you're emulating what one would do in lisp, the code would be
something like:

int
sumOnlyNumbers(
iterator begin,
iterator end,
int sum = 0 )
{
return begin == end
? sum
: sum_only_numbers(
++ begin, end,
( is_num( *begin )
? sum + to_num( *begin )
: sum ) ) ;
}

(One of the nice things about C++ is that it supports so many
different idioms. Including functional programming.)

But I wouldn't consider that really an acceptable solution in
C++. C++ has natural looping constructs which means that you
don't have to do things the hard way.

and you have to call it as

sum_only_numbers (list.begin (), list.end (), 0);

Unless you provide a default argument for the last parameter.

 

[Balog Pal]

"James Kanze"

If you're emulating what one would do in lisp, the code would be

something like:

int
sumOnlyNumbers(
iterator begin,
iterator end,
int sum = 0 )
{
return begin == end
? sum
: sum_only_numbers(
++ begin, end,
( is_num( *begin )
? sum + to_num( *begin )
: sum ) ) ;
}

It looks nice, but IMO you use 'begin' for both read and write, thus the
result is undefined or unspecified...

(One of the nice things about C++ is that it supports so many

different idioms. Including functional programming.)

To some level at least, unfortunetely recursion is not guaranteed to work
even for an iterative process, as that is left as QoI issue.

But I wouldn't consider that really an acceptable solution in

C++. C++ has natural looping constructs which means that you
don't have to do things the hard way.

Interesting this 'hard way' -- where the problem has recursion naturally,
actually the conversion to some other form is the hard thing. To do, and
later to read, review, understand... while the original is just
self-evident.

 

[James Kanze]

"James Kanze"

something like:

int
sumOnlyNumbers(
iterator begin,
iterator end,
int sum = 0 )
{
return begin == end
? sum
: sum_only_numbers(
++ begin, end,
( is_num( *begin )
? sum + to_num( *begin )
: sum ) ) ;
}

It looks nice, but IMO you use 'begin' for both read and
write, thus the result is undefined or unspecified...

Ouch. You're right---it's undefined behavior. The "++ begin"
would have to be "begin + 1" (which is more in keeping with the
functional programming idiom anyway, but which requires random
access iterators).

To some level at least, unfortunetely recursion is not
guaranteed to work even for an iterative process, as that is
left as QoI issue.

Recursion is guaranteed to work. How deep you can recurse is a
QoI issue, of course, but then, so is everything else which
involves resources.

Interesting this 'hard way' -- where the problem has recursion
naturally, actually the conversion to some other form is the
hard thing.

In this case, recursion is being used to "iterate"---the C++
construct for iteration is a loop, and in general, a loop is
more expressive ("simpler") than recursion, when you want to
loop, since it says exactly what you want to do. Other problems
do express themselves more naturally as recursion: using a loop
to calculate factorial can be considered "the hard way" (even if
it is recommended for space and performance reasons).

To do, and later to read, review, understand... while the
original is just self-evident.

What's more self-evident than using std::accumulate (which is
obviously what one would do in production code). And what's
more evident than a loop to implement something like
std::accumulate---it's what loops are designed for.

 

[Michael DOUBEZ]

Except that using recursion for this in C++ is what I would
consider bad programming practice.

As the OP said, it is just an exercise:
"Hello, need to do some exercices that involves recursion, the
substitution model in particular (I believe that what it's called).[...]

If he really wanted to do it the c++ way, he would have used
std::accumulate() with a custom operator.

[...]

The is_num and to_num could be merged into the faillible class
idiom:

If they're just for this one program, it's sufficient that
to_num return 0 if the value isn't a number.

Given the first shot he gave,I assumed the OP wanted to keep the
structure of the algorithm.