Ricorsione in C

ProgrammaGat

il 12 giu 2020, 12:06

43 risposte

43 Risposte - Pagina 2

Andrea Quaglia

Molto attivo

Iscritto da: giu, 2017

Messaggi:: 614

Re: Ricorsione in C

12 giu 2020, 18:51

Uno non si si può assentare un mezzo pomeriggio che... va bé, avete messo tutti la vostra, ci metto anche la mia!

#include <stdio.h>
#include <stdlib.h>

int stringa_ord(char *s){
    // stringa vuota
    if (*s == '\0')
        return 0;
    // stringa di 1 solo carattere
    if (*(s+1) == '\0')
        return 1;
    if (*s <= *(s+1))
        return stringa_ord(s+1);
    else
        return 0;
}

int main()
{
    char strg2test[] = "abcccccccccde";

    printf("%s: %s\n", strg2test, stringa_ord(strg2test) ? "ordinata" : "non ordinata");
    return 0;
}

StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
12 giu 2020, 18:52
Visto che è banale mostralo, grazie

Naturalmente rispondevo a migliorabile
Weierstrass
Utente Famoso
Iscritto da
feb, 2019
Messaggi:
2248
Re: Ricorsione in C
12 giu 2020, 18:52
@migliorabile

Vabbè ma che pesantezza però.

Se proprio devo dire la mia, personalmente non utilizzerò mai la programmazione ricorsiva, perché solitamente sono a corto di ram e poi mi devo fidare ciecamente del compilatore, come hai scritto tu stesso. La fiducia è cosa buona e giusta, ma non quando ci sono alternative percorribili.

Per quanto riguarda l'OP va benissimo tutto: più esempi fate meglio sarà per lui
StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
12 giu 2020, 20:06
Intanto che aspettiamo la versione ricorsiva banale che dovrebbe arrivare a breve

metto qui la mia versione ricorsiva non banale
Io meglio di così non riesco, aspetto magari consigli
```
_Bool ordinatar(char * s)
{
   // versione ricorsiva
   if(!s)
      return 0;

   if(*(s + 1))
   {
      if(*s > *(s + 1))
      {
         return 0;
      }

      else
      {
         return ordinatar(s + 1);
      }
   }

   return 1;
}
```
A
Alexv
Molto attivo
Iscritto da
giu, 2018
Messaggi:
646
Re: Ricorsione in C
12 giu 2020, 22:14
```
if (*(s+1))
```
Non mi sembra corretta come condizione di uscita. Comunque una versione "più banale" potrebbe prevedere le [ ] come si fa con gli array.
StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
12 giu 2020, 22:25
Ma ti riferisci a me?

Se non sei sicuro provala

Così vediamo se va o no
StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
12 giu 2020, 22:28
Alexv ha scritto:
Non Comunque una versione "più banale" potrebbe prevedere le [ ] come si fa con gli array.
Temo richiederebbe una variabile in più

E quindi perderemmo la velocità ed efficenza della, non ancora arrivata, versione banale
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Ricorsione in C
12 giu 2020, 23:45
Se vi capita dite a StandardOil che:
- quell'else è superfluo;
- *s e *(s+1) corrispondono rispettivamente a s[0] e s[1];
- in caso di stringa vuota va a leggere zone di memoria che non competono all'array.
A
Alexv
Molto attivo
Iscritto da
giu, 2018
Messaggi:
646
Re: Ricorsione in C
13 giu 2020, 00:29
Non volevo mettere zizzania, avevo intenzione di postare la versione di Quaglia, solo che con le quadre invece che con l'asterisco.
Sull'if mi riferivo alla sola sintassi, avevo dimenticato che \0 corrispondesse a zero.
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricorsione in C
13 giu 2020, 05:51
```
int is_ordered(char* s) {
    return !(s[0] && s[1]) || (s[0] <= s[1]) && is_ordered(s+1);
}

int is_ordered(char* s) {
    return !(*s && *(s+1)) || (*s <= *(s+1)) && is_ordered(s+1);
}
```
Scritta in questo modo, un buon compilatore la convertirebbe in un ciclo.

@StandardOil: la tua versione HA DIVERSI ERRORI!!!
Gestisci in modo ERRATO la base (anzi le basi) della ricorsione.
StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
13 giu 2020, 07:12
Visto che funziona ne dubito che sia errata, ma comunque mi fido, basta che mi spieghi i miei errori

Riguardo al confronto con la versione iterativa:
Una chiamata di funzione, un not, due and, un or e un test dovrebbero essere più semplici di un while con un solo test (vero, due, c'è il test implicito nel while) e un not 'fuori' dal ciclo?
Se ne sei convinto sono pronto a crederci, come anche mi fido che un buon compilatore riesca a trasformare le chiamate in cicli, ma posso non fidarmi di quanto io sia bravo a 'tarare' il compilatore ?

Preferisco pensare 'easy' io piuttosto che sperare che lo faccia una macchina per me

mi sembra comunque corretto aggiungere una cosa:
io nel mio primo post ho segnalato che sarebbe stato utile per la ricorsione passare un puntatore incrementato di uno
sei stato tu a dire che sarebbe stato un errore, hai usato anche le maiuscole, cosa che è sembrata un po' aggressiva, almeno ai miei occhi
e poi tu stesso usi un puntatore incrementato di uno?
e lo fai non solo nella versione coi puntatori
ma anche nella versione che usa gli indici?

scusa ma mi sembra che idee chiare e coerenza non siano il tuo forte
qui tutto scritto è, basta rileggere

Ho parlato
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricorsione in C
13 giu 2020, 08:37
Visto che funziona ne dubito che sia errata, ma comunque mi fido, basta che mi spieghi i miei errori
No, non funziona.

La battuta alla Kruill non te la puoi permettere, non sei sbbastanza saggio
StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
13 giu 2020, 08:43
Ti troverai bene in compagnia di Supermanpc, nippolo e theorlav?

Non lo saprò mai
StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
13 giu 2020, 09:46
Alexv ha scritto:
Non volevo mettere zizzania, avevo intenzione....
in effetti io non avevo vissuto molto bene il tuo precedente messaggio, spero tu non ti sia offeso;
nel caso faccio ammenda, non volevo, me ne dispiacerebbe

comunque mi è venuto in mente un caso per il quale la tua domanda avrebbe senso:
se la stringa fosse di lunghezza 1 (il solo terminatore)
fare *(s+1) riferirebbe al primo elemento "dopo" la stringa, in area di memoria non 'giusta'
in effetti ci avevo pensato, scrivendolo, e sapevo che non sarebbe stato un problema, ma poi avevo soprasseduto
mi hai messo la pulce nell'orecchio e quindi ci ho pensato:

non è un problema!
la mia è un'affermazione, non un'ipotesi

formalmente è vero che indirizzo area di memoria fuori da una eventuale stringa corta, ma fin del K&R è formalmente garantito che l'aritmetica dei puntatori si applica anche 'almeno' al primo elemento 'dopo' la fine dell'array, quindi formalmente non ci sono problemi
dato che io 'leggo solo' la posizione di memoria incriminata non ci sarebbero problemi nemmeno in eventuali altre parti del programma
rimane il fatto che leggo comunque un carattere sbagliato
ma delle due l'una:
o il carattere sbagliato è differente da 0 binario, e quindi siccome segue uno zero binario sarebbe una stringa non crescente, return falso
oppure si tratterebbe di uno zero binario, nel caso sarebbe trattato come terminatore che non sarebbe strettamente crescente col terminatore 'vero' della stringa e il tutto comunque finirebbe con un return 0
ieri tutto questo lo sapevo, ma non riuscivo a metterlo a parole, un grazie a te che mi ci hai fatto pensare esplicitamente
A
Alexv
Molto attivo
Iscritto da
giu, 2018
Messaggi:
646
Re: Ricorsione in C
13 giu 2020, 10:17
E' quello che ha detto anche migliorabile (anche a me ha instillato la pulce insieme a Nippolo, altrimenti non ci avrei pensato). Il problema è che il terminatore di stringhe non è un modo sicuro per far terminare la ricorsione, perché dopo potrebbe esserci qualunque cosa.
Credo che la versione più sicura sia quella che non vada a controllare oltre il \0, magari portandosi dietro la lunghezza della stringa, o, per una versione meno pesante, un indice, ma sempre usando due funzioni.
```
#include <stdlib.h>
#include <stdio.h>
#pragma warning(disable : 4996)

int _controllo(char* s, int i)
{
	if (!s) return 0;
	else if (s[i] == '\0') 
		return 1;
	else if (i == 0) 
		return _controllo(s, i + 1);
	else if (s[i] < s[i - 1]) 
		return 0;
	else 
		return _controllo(s, i + 1);
}
int controllo(char* s)
{
	return _controllo(s, 0);
}

int main()
{
	char s[6];
	printf("Inserisci stringa ");
	scanf("%s", s);
	if (controllo(s))
		printf("Ordinata \n");
	else
		printf("Non ordinata \n");
	return EXIT_SUCCESS;
}
```

Devi accedere o registrarti per scrivere nel forum

43 risposte