Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Janis Papanagnou <janis_papanagnou+ng@hotmail.com>
Newsgroups: comp.lang.c
Subject: Re: Recursion, Yo
Date: Tue, 9 Apr 2024 14:27:19 +0200
Organization: A noiseless patient Spider
Lines: 40
Message-ID: <uv3c77$7eb5$1@dont-email.me>
References: <uut24f$2icpb$1@dont-email.me> <uutqd2$bhl0$1@i2pn2.org>
 <uv2u2a$41j5$1@dont-email.me> <uv2v2o$42fo$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 09 Apr 2024 12:27:20 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e5402271be07e4c30967281c98e603b9";
	logging-data="244069"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19IS55XBQJs1T+DBzu2eRzW"
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
 Thunderbird/45.8.0
Cancel-Lock: sha1:hHhqU6clBgS6h5Pjsa4gsM4IYQE=
X-Enigmail-Draft-Status: N1110
In-Reply-To: <uv2v2o$42fo$3@dont-email.me>
Bytes: 2768

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. :-)

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).

Janis

[*] 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_ }

which is also very fast for larger arguments, while the implementation
still being within the (non-imperative) recursive functions paradigm.

PS: I hope *this* scared you at least a bit, since that was one of the
original purposes of the post. ;-)

PPS: Rewrite to "C" left as an exercise to the reader.