Path: ...!3.eu.feeder.erje.net!feeder.erje.net!news2.arglkargh.de!news.mixmin.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 13:25:51 +0100
Organization: A noiseless patient Spider
Lines: 72
Message-ID: <877ch6soxc.fsf@bsb.me.uk>
References: <uut24f$2icpb$1@dont-email.me> <uutqd2$bhl0$1@i2pn2.org>
	<uv2u2a$41j5$1@dont-email.me> <87edbestmg.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Tue, 09 Apr 2024 12:25:53 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="fa324957339a8e3c51ed3c4958d6166a";
	logging-data="243622"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+W3NUekOYg8+3wjuiVd/ySuRplT1kHEts="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:BhhsCZLEjwDr89Ibk3BAbs9OpJU=
	sha1:ePNU8NQfEFYj4Rq8bbIdqB2rvPk=
X-BSB-Auth: 1.bb81fd415cb00a01fa60.20240409132551BST.877ch6soxc.fsf@bsb.me.uk
Bytes: 3562

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
>
>> On 07.04.2024 11:52, fir wrote:
>>>>
>>> okay, there are some class of things that suit good for recursion - and
>>> its probably good to spot whose they are
>>
>> All iterations. (So, basically all code we typically write with 'for'
>> and 'while' loops.) For example. Plus all the things where emulation
>> with non-recursive means is cumbersome and complex. (Like operating
>> on recursive data structures like trees.)
>>
>> Actually, you can formally derive the iterative constructs from [a
>> subset of] the recursive ones (by introducing variables and loops).
>>
>> It makes a difference where one comes from. If folks learned coding
>> from imperative languages they have more problems with a functional
>> view (and also with recursion, it seems). Here, with "C", we're more
>> used to 'while' loops and variables, I think.
>
> The language used is key.  I would not say that recursion is a good fit
> for "all iterations" when using C.  It's significant (or at least note
> worthy) that the code in the original post was not ISO C and re-writing
> it in ISO C would show up some of the issues involved, though this task
> is still a good fit for an explicitly recursive solution.

Though I want to say that for many application in standard C the use of
a "visitor function" makes the OP's code awkward.  Instead, I would
probably iterate over the permutations like this:

#include <stdbool.h>
#include <stdio.h>

void swap(int *a, int *b)
{
     int t = *a; *a = *b; *b = t;
}

bool next_perm(int n, int *p)
{
     int i = n - 2;
     while (i >= 0 && p[i] >= p[i+1]) i--;
     // i is now -1 or the largest index with p[i] < p[i+1]
     if (i < 0)
          return false;
     int j = n - 1;
     while (p[j] <= p[i]) j--;
     // j is now the largest index > i with p[j] > p[i]
     swap(&p[i], &p[j]);
     // reverse p[i+1] ... p[n-1]
     int l = i, h = n;
     while (++l < --h)
          swap(&p[l], &p[h]);
     return true;
}

int main(int argc, char **argv)
{
     if (argc > 1) {
          int n = argc - 1, idx[n];
          for (int i = 0; i < n; i++)
               idx[i] = i;
          do for (int i = 0; i < n; i++)
                  printf("%s%s", argv[idx[i] + 1], i == n-1 ? "\n" : " ");
          while (next_perm(n, idx));
     }
}

-- 
Ben.