Re: Recursion, Yo

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: Recursion, Yo
Date	2024-04-09 15:27 +0100
Organization	A noiseless patient Spider
Message-ID	<871q7esjbc.fsf@bsb.me.uk> (permalink)
References	<uut24f$2icpb$1@dont-email.me> <uutqd2$bhl0$1@i2pn2.org> <uv2u2a$41j5$1@dont-email.me> <uv2v2o$42fo$3@dont-email.me> <uv3c77$7eb5$1@dont-email.me>

Show all headers | View raw

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:

> On 09.04.2024 10:43, Lawrence D'Oliveiro wrote:
>> 
>> One of the first few books I ever read on Comp Sci (while still at school, 
>> back when schools didn’t have computers) was “A Comparative Study Of 
>> Programming Languages” by Bryan Higman. In one of the chapters, I came 
>> across the concept of recursion. I also came across Ackermann’s Function.
>> 
>> Let’s just say that, after staring into that abyss, nothing about 
>> recursion could possibly scare me, ever again ...
>
> Well, Ackermann is a good example how to scare folks - especially
> if folks implement it straightforward recursively, then running it
> and waiting for termination. :-)

Ackemann's function in FORTRAN (which had no recursion in those days)
used to be a student programming assignment.  Not so much scary as a
good learning exercise.

> But there's also less complex algorithms, like Fibonacci, that have
> a bad runtime complexity if implemented in a trivial way. Though that
> depends on how you actually implement it[*] and it's not an inherent
> [bad] property of recursion (as sometimes wrongly assumed).

Yes.  Haskell's

  fib = 1 : 1 : zipWith (+) fib (tail fib)

is (in Haskell terms) quite efficient.

> [*] I once wrote (for an "obfuscated Awk" post) the usual definition
> (with some nasty side-effects, granted), which basically was
>
>   func __(_){return _>2?__(--_)+__(--_):1}
>
> The (for this thread) noteworthy detail is that you can transform the
> function to
>
>   func ___(_) { return __(_,x^x,x^x^x) }
>   func __(_,_x,x_) { return --_?__(_,x_,_x+x_):_x+x_ }

The trouble with AWK (without gawk's -M) is that functions like this
just start to give a wrong, but plausibly sized, result.  For example
___(80) is 23416728348467684 when it should be 23416728348467685.

-- 
Ben.

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

Thread

Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-07 02:58 +0000
  Re: Recursion, Yo fir <fir@grunge.pl> - 2024-04-07 11:52 +0200
    Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-09 10:25 +0200
      Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-09 08:43 +0000
        Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-09 14:27 +0200
          Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-09 15:27 +0100
            Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-09 21:55 +0200
              Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-09 13:31 -0700
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-10 08:30 +0200
        Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-09 15:02 +0100
      Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-09 11:44 +0100
        Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-09 13:25 +0100
        Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-10 01:50 +0000
          Re: Recursion, Yo "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-04-09 20:54 -0700
          Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-10 09:11 +0200
            Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-10 07:52 +0000
              Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-10 11:18 +0200
                Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-10 13:42 +0100
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-10 16:46 +0200
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-11 00:18 +0000
                Re: Recursion, Yo Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-11 00:54 +0000
                Heh heh...  (Was: Recursion, Yo) gazelle@shell.xmission.com (Kenny McCormack) - 2024-04-11 08:00 +0000
                Re: Heh heh...  (Was: Recursion, Yo) Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-11 15:13 +0000
                Re: Heh heh...  (Was: Recursion, Yo) gazelle@shell.xmission.com (Kenny McCormack) - 2024-04-11 19:06 +0000
                Re: Recursion, Yo Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-11 15:04 +0000
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-11 20:47 +0200
                Re: Recursion, Yo scott@slp53.sl.home (Scott Lurndal) - 2024-04-11 15:15 +0000
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-12 02:31 +0000
                Re: Recursion, Yo Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-12 03:51 +0000
                Re: Recursion, Yo cross@spitfire.i.gajendra.net (Dan Cross) - 2024-04-12 12:51 +0000
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-12 07:32 +0200
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-12 09:30 +0200
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-12 15:03 +0200
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-12 16:51 +0200
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-13 19:17 +0200
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-13 20:04 +0200
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-13 00:10 +0000
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-12 07:34 +0000
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-12 14:35 +0200
                Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-12 16:42 +0100
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-13 00:13 +0000
                Re: Recursion, Yo Michael S <already5chosen@yahoo.com> - 2024-04-13 20:33 +0300
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-14 00:23 +0100
                Re: Recursion, Yo Michael S <already5chosen@yahoo.com> - 2024-04-14 03:29 +0300
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-15 15:07 +0200
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-15 08:46 -0700
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-15 17:47 +0100
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-15 12:00 -0700
                Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-15 20:24 +0100
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-15 21:37 +0100
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-15 22:39 +0200
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-15 22:54 +0200
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-15 14:25 -0700
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-14 00:29 +0000
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-13 20:05 -0700
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-13 19:37 +0200
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-14 00:28 +0000
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-14 11:17 +0100
                Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-14 13:51 +0100
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-14 22:47 +0100
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-14 22:44 +0000
                Re: Recursion, Yo "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-04-14 20:35 -0700
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-15 17:50 +0100
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-15 22:30 +0000
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-17 18:09 +0100
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-17 22:12 +0000
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-22 18:06 +0200
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-15 20:36 +0200
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-15 22:32 +0000
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-22 17:41 +0200
                Re: Recursion, Yo Michael S <already5chosen@yahoo.com> - 2024-04-16 23:11 +0300
                Re: Recursion, Yo Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-19 08:26 -0700
                Re: Recursion, Yo scott@slp53.sl.home (Scott Lurndal) - 2024-04-19 18:25 +0000
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-19 12:15 -0700
                Re: Recursion, Yo Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-20 05:55 -0700
                Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-19 19:34 +0100
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-20 02:11 +0100
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-19 18:24 -0700
                Re: Recursion, Yo Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-20 15:35 +0000
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-19 12:18 -0700
                Re: Recursion, Yo Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-20 06:03 -0700
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-22 17:49 +0200
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-15 17:50 +0100
                Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-12 10:38 +0100
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-12 15:07 +0200
                Re: Recursion, Yo bart <bc@freeuk.com> - 2024-04-12 16:38 +0100
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-12 19:06 -0700
                Re: Recursion, Yo Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 07:46 -0700
                Re: Recursion, Yo scott@slp53.sl.home (Scott Lurndal) - 2024-04-11 14:36 +0000
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-11 10:15 +0200
                Re: Recursion, Yo Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-04-11 12:37 -0700
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-12 09:38 +0200
                Re: Recursion, Yo fir <fir@grunge.pl> - 2024-04-14 20:34 +0200
                Re: Recursion, Yo Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-04-10 15:18 +0200
                Re: Recursion, Yo scott@slp53.sl.home (Scott Lurndal) - 2024-04-10 14:23 +0000
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-11 00:16 +0000
                Re: Recursion, Yo scott@slp53.sl.home (Scott Lurndal) - 2024-04-11 14:34 +0000
                Re: Recursion, Yo Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-04-12 00:04 +0100
                Re: Recursion, Yo Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-10 17:19 +0000
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-10 21:19 +0200
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-11 00:54 +0000
                Re: Recursion, Yo Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-11 02:06 +0000
                Re: Recursion, Yo David Brown <david.brown@hesbynett.no> - 2024-04-11 10:23 +0200
                Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-11 08:34 +0000
            Re: Recursion, Yo Kaz Kylheku <643-408-1753@kylheku.com> - 2024-04-10 17:10 +0000
          Re: Recursion, Yo Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-10 10:14 -0700
  Re: Recursion, Yo Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-04-09 08:44 +0000

csiph-web