Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: Why does this work on Xcode ???
Date: Sat, 10 Aug 2019 09:29:17 -0700
Organization: A noiseless patient Spider
Lines: 99
Message-ID: <86pnld7zmq.fsf@mailhub.linuxsc.com>
References: <1b10612f-47b9-4097-be59-d00dec4a800b@googlegroups.com> <qgnd93$tap$1@dont-email.me> <slrnqj8jqf.cdo.grahn+nntp@frailea.sa.invalid>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="4bad90a7c43721789c432acb03dbc8ee"; logging-data="13248"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18NUHe5jeMnn6K5Bl1jdiAmKRpxJ0Dp3W8="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:Yu86J7QaRkRboUMtpgseoCT/xM8= sha1:8mUkhLc0LKjYwidK+sbiDZFkahI=
Xref: csiph.com comp.lang.c++:67530

Jorgen Grahn <grahn+nntp@snipabacken.se> writes:

> On Wed, 2019-07-17, Alf P. Steinbach wrote:
>
>> On 17.07.2019 07:03, Bob Langelaan wrote:
>>
>>> Several of my students have submitted the following solution (or
>>> something very similar) for a recursive function to add the contents
>>> of an array:
>>
>> The presented code doesn't ?add the contents?, I guess that's just typo.
>>
>>
>>> // Returns true if the supplied value is found in the array of values
>>> // and false otherwise
>>> template <typename type, size_t size>
>>> bool isMember(const array<type,size> & myArray, const int n, const type value)
>>> {
>>> 	if ( n < 0 )
>>> 	{
>>> 		return false;
>>> 	}
>>> 	else if ( myArray[n] == value )
>>> 	{
>>> 		return true;
>>> 	}
>>> 	return isMember( myArray, n - 1, value );
>>> }
>>
>> The two main problems with this function are:
>>
>> * Passing `value` by value may incur severe copying inefficiency.
>> * The tail recursion may easily consume all stack space and yield UB.
>
> It's also fairly sad and inelegant use of recursion, with the extra
> cursor being passed around.  The way I learned recursion, you start by
> seeing an array as either empty, or having a head element, and then:
>
>   // vaguely Haskell-like pseudo-code
>   ismember(value, []) -> false
>   ismember(value, head:tail) -> value==head || ismember(value, tail)
>
> My point is, I'm not sure the students will appreciate recursion
> properly based on that code, if that's the intention.  (Perhaps not
> based on any C++ code.)

These comments strike me as somewhat odd.  Certainly it is true
that recursive functions often offer a good fit to recursive data
types.  That doesn't mean recursion is a bad fit in other cases.
On the contrary, using recursion often gives a definition that is
simpler and easier to understand than a non-recursive version.  A
well-known example is finding the greatest common divisor of two
numbers, which might be written as follows (with gcd(0,0) to
return the value 1):

    unsigned
    gcd( unsigned a, unsigned b ){
        return  a == 0 ?    b != 0 ? b : 1
            :   gcd( b%a, a );
    }

Writing a nicely tail-recursive function often entails passing
arguments besides just the primary data item.  This happens with
arrays in C and C++ because arrays are not recursive data types in
C or C++ (nor are they in many functional languages).  Furthermore
we may want not one additional "cursor" but more than one.  Here
is a function to determine if a sorted array contains a given
value:

    bool
    contains( int *v, size_t base, size_t limit, int item ){
        if(  base == limit  )  return  false;

        size_t mid = base + (limit-base)/2;

        if(  v[mid] < item  )  return  contains( v, mid+1, limit, item );
        if(  v[mid] > item  )  return  contains( v, base,  mid,   item );

        return  true;
    }

In later versions of C++ we might choose to write this function
differently, using 'span' (disclaimer: I am not an expert on
span!).  Doing that would very likely give a nicer function.  But
I wouldn't say the non-span version is "inelegant".  It's just a
reflection of how the language-provided data types work.  Do I
remember right that you are one of the people who is still
working (or forced to work) with C++11?  Anyone in that boat
might choose a function definition like the one above, until such
time as better language facilities are available so it could be
re-written more attractively.

I guess my main point is that recursion is more broadly applicable
than just those situations where recursive data types are
involved.  In fact, in languages like C and C++, it is much more
likely to encounter a good fit for recursion that does not make
use of recursive data types, simply because C and C++ typically do
not define data types recursively.  Recursion is more fundamental
than just the cases where recursive data types are used.