Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #67530

Re: Why does this work on Xcode ???

Show key headers only | View raw

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.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Why does this work on Xcode ??? Bob Langelaan <bobl0456@gmail.com> - 2019-07-16 22:03 -0700
  Re: Why does this work on Xcode ??? Paavo Helde <myfirstname@osa.pri.ee> - 2019-07-17 08:46 +0300
  Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 00:06 -0700
    Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 01:44 -0700
  Re: Why does this work on Xcode ??? Juha Nieminen <nospam@thanks.invalid> - 2019-07-17 07:46 +0000
  Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-07-17 09:12 -0400
  Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 17:01 +0200
    Re: Why does this work on Xcode ??? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-07-17 22:15 +0100
      Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 23:29 +0200
        Re: Why does this work on Xcode ??? Christian Gollwitzer <auriocus@gmx.de> - 2019-07-19 08:27 +0200
          Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:09 +0200
            Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:24 +0200
            Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 11:18 -0700
              Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-10 21:05 +0200
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-22 10:28 -0700
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-22 19:50 +0200
                Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-22 23:45 +0100
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 07:22 +0200
                Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-23 13:12 +0100
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 16:02 +0200
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-09-18 08:50 -0700
                Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 09:28 -0400
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-23 16:37 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 23:07 +0200
                Re: Why does this work on Xcode ??? Richard Damon <Richard@Damon-Family.org> - 2019-08-23 19:10 -0400
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:49 +0200
                Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 19:49 -0400
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:45 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 12:06 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:25 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:11 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 17:12 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 23:32 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-26 11:51 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-26 13:26 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 11:36 +0200
                Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:27 +0200
                Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:15 +0200
                Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-26 00:43 -0400
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-24 04:58 -0700
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-26 09:53 -0700
                Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-28 18:03 -0700
          Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-19 00:20 -0700
          Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-09 07:41 -0700
      Re: Why does this work on Xcode ??? Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-24 19:49 +0200
    Re: Why does this work on Xcode ??? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-07-21 11:41 +0000
      Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 09:29 -0700

csiph-web