Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.lang.c
Subject: Re: Recursion, Yo
Date: Tue, 09 Apr 2024 15:27:03 +0100
Organization: A noiseless patient Spider
Lines: 48
Message-ID: <871q7esjbc.fsf@bsb.me.uk>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 09 Apr 2024 14:27:05 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="fa324957339a8e3c51ed3c4958d6166a";
	logging-data="299724"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19eZEcpBRPRNd5wVxcze2820G/E4Kk/pho="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:UoGOQ0tgI50CZ6g3CeDc5oSMkiU=
	sha1:/zArULlq19B7/FzZF8T+XsgWykY=
X-BSB-Auth: 1.3120ae427139f28b88b3.20240409152703BST.871q7esjbc.fsf@bsb.me.uk
Bytes: 3059

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.