Ricorsione in C

ProgrammaGat

il 12 giu 2020, 12:06

43 risposte

43 Risposte - Pagina 3

StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
13 giu 2020, 10:21
Quello che dice migliorabile non mi interessa in nessun caso, grazie comunque per averlo riportato

Che l'uso spregiudicato dell'aritmetica dei puntatori sembri un problema, ma non lo sia, lo ho già dimostrato

La tua versione è chiara e sicura, ne convengo, ma come affermavo ieri richiede una variabile in più...
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricorsione in C
13 giu 2020, 12:02
Comportamento un po' sciocco. Ma va bene lo stesso

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2248

Re: Ricorsione in C

13 giu 2020, 12:25

migliorabile ha scritto:
@Weierstrass, tanto per dimostrare chi c'e' l'ha piu' corto
(SI, lo so! Ma si puo' fare lo stesso Pensa bene a come funzionano gli operatori booleani)
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.

Ottimo esempio

Io però rimango sempre dubbioso sui compilatori. Ho provato con due pesi massimi ed in entrambe la stack cresce inesorabilmente

Codice


#include "stdio.h"
int is_ordered(char* s) {
    return !(s[0] && s[1]) || (s[0] <= s[1]) && is_ordered(s+1);
}
int main(){
  char s[20] = "est";
  int a = is_ordered(s);
  printf("%d", a);
  return 0;
}

IAR, ARM, Optimization High


int is_ordered(char* s) {
is_ordered:
       0x1d40: 0xb580         PUSH      {R7, LR}
    return !(s[0] && s[1]) || (s[0] <= s[1]) && is_ordered(s+1);
       0x1d42: 0x7802         LDRB      R2, [R0]
       0x1d44: 0x2a00         CMP       R2, #0
       0x1d46: 0xbf1c         ITT       NE
       0x1d48: 0x7841         LDRBNE    R1, [R0, #0x1]
       0x1d4a: 0x2900         CMPNE     R1, #0
       0x1d4c: 0xd009         BEQ.N     0x1d62
       0x1d4e: 0x4291         CMP       R1, R2
       0x1d50: 0xd309         BCC.N     0x1d66
       0x1d52: 0x1c40         ADDS      R0, R0, #1
       0x1d54: 0xf7ff 0xfff4  BL        is_ordered              ; 0x1d40
       0x1d58: 0x1e40         SUBS      R0, R0, #1
       0x1d5a: 0x4180         SBCS      R0, R0, R0
       0x1d5c: 0x43c0         MVNS      R0, R0
       0x1d5e: 0x0fc0         LSRS      R0, R0, #31
       0x1d60: 0xbd02         POP       {R1, PC}
       0x1d62: 0x2001         MOVS      R0, #1
       0x1d64: 0xbd02         POP       {R1, PC}
       0x1d66: 0x2000         MOVS      R0, #0
       0x1d68: 0xbd02         POP       {R1, PC}
       0x1d6a: 0x0000         MOVS      R0, R0

gcc, x86, Optimization -O3


!int is_ordered(char* s) {
is_ordered+0: push   %ebp
is_ordered+1: mov    %esp,%ebp
is_ordered+3: sub    $0x18,%esp
!    return !(s[0] && s[1]) || (s[0] <= s[1]) && is_ordered(s+1);
is_ordered()
is_ordered+6: mov    0x8(%ebp),%eax
is_ordered+9: movzbl (%eax),%eax
is_ordered+12: test   %al,%al
is_ordered+14: je     0x4014cb <is_ordered+66>
is_ordered+16: mov    0x8(%ebp),%eax
is_ordered+19: add    $0x1,%eax
is_ordered+22: movzbl (%eax),%eax
is_ordered+25: test   %al,%al
is_ordered+27: je     0x4014cb <is_ordered+66>
is_ordered+29: mov    0x8(%ebp),%eax
is_ordered+32: movzbl (%eax),%edx
is_ordered+35: mov    0x8(%ebp),%eax
is_ordered+38: add    $0x1,%eax
is_ordered+41: movzbl (%eax),%eax
is_ordered+44: cmp    %al,%dl
is_ordered+46: jg     0x4014d2 <is_ordered+73>
is_ordered+48: mov    0x8(%ebp),%eax
is_ordered+51: add    $0x1,%eax
is_ordered+54: mov    %eax,(%esp)
is_ordered+57: call   0x401489 <is_ordered>
is_ordered+62: test   %eax,%eax
is_ordered+64: je     0x4014d2 <is_ordered+73>
is_ordered+66: mov    $0x1,%eax
is_ordered+71: jmp    0x4014d7 <is_ordered+78>
is_ordered+73: mov    $0x0,%eax
!}
is_ordered+78: leave  
is_ordered+79: ret

Poi vabbè, sono questioni di lana caprina su un PC o su un qualsiasi processore che non abbia una RAM infima

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Ricorsione in C
13 giu 2020, 12:29
Con gente che, volutamente o meno, ignora i post altrui, a dir la verità un po' la voglia passa...

In ogni caso non posso esimermi dal dovere di far notare ad un utente che sta sbagliando... quindi:
StandardOil ha scritto:
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'
...
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
Quello che dici non ha senso, considera infatti il seguente frammento di codice:
```
if(*s > *(s + 1))
{
    return 0;
}
else
{
    return ordinatar(s + 1);
}
```
Nel caso di stringa vuota avremo che alla prima chiamata ricorsiva la condizione dell'if si traduce in 0>s[1]; ora non so se s[1] viene interpretato come signed o unsigned, ma fatto sta che quella condizione può tranquillamente essere falsa e quindi la ricorsione continuerebbe andando a leggere ancora altre zone di memoria "non giuste".

Quindi caro @StandardOil facci (e soprattutto fatti) un favore... almeno la logica rimuovila dalla tua lista degli ignorati!
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricorsione in C
13 giu 2020, 12:40
@Weiestrass, ho appena controllato. Il GCC supporta l'ottimizzazione per la "tail recursion".
Da quanto capisco, pero' serve attivare un flag specifico: "-foptimize-sibling-calls".

Ho banalmente cercaco con google: "gcc tail recursion optimization". Ad esempio:

https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

ma trovi diversi link che ne parlano.

La tail recursion e' una tecnica standard nei linguaggi funzionali. C e C++ non sono ""specificatamente"" funzionali, quindi abilitare questo tipo di ottimizzazone non ha molto senso perche' non serve nel 99.999999999999% dei casi.

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2248

Re: Ricorsione in C

13 giu 2020, 13:14

migliorabile ha scritto:
@Weiestrass, ho appena controllato. Il GCC supporta l'ottimizzazione per la "tail recursion".
Da quanto capisco, pero' serve attivare un flag specifico: "-foptimize-sibling-calls".

Ho banalmente cercaco con google: "gcc tail recursion optimization". Ad esempio:

https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

ma trovi diversi link che ne parlano.

La tail recursion e' una tecnica standard nei linguaggi funzionali. C e C++ non sono ""specificatamente"" funzionali, quindi abilitare questo tipo di ottimizzazone non ha molto senso perche' non serve nel 99.999999999999% dei casi.

Ho provato -O3 -foptimize-sibling-calls

mi sembra che ma lo stack che cresce ci sia sempre

!int is_ordered(char* s) {
is_ordered+0: push   %ebx
is_ordered+6: sub    $0x18,%esp
is_ordered+9: mov    0x20(%esp),%edx
!    return !(s[0] && s[1]) || (s[0] <= s[1]) && is_ordered(s+1);
is_ordered+1: mov    $0x1,%eax
is_ordered+13: movzbl (%edx),%ecx
is_ordered+16: test   %cl,%cl
is_ordered+18: je     0x4014a2 <is_ordered+34>
is_ordered+20: movzbl 0x1(%edx),%ebx
is_ordered+24: test   %bl,%bl
is_ordered+26: je     0x4014a2 <is_ordered+34>
is_ordered+28: xor    %eax,%eax
is_ordered+30: cmp    %bl,%cl
is_ordered+32: jle    0x4014b0 <is_ordered+48>
is_ordered()
is_ordered+48: movzbl 0x2(%edx),%ecx
is_ordered+52: mov    $0x1,%eax
is_ordered+57: test   %cl,%cl
is_ordered+59: je     0x4014a2 <is_ordered+34>
is_ordered+61: xor    %eax,%eax
is_ordered+63: cmp    %cl,%bl
is_ordered+65: jg     0x4014a2 <is_ordered+34>
is_ordered+67: add    $0x2,%edx
is_ordered+70: mov    %edx,(%esp)
is_ordered+73: call   0x401480 <is_ordered>
is_ordered+78: test   %eax,%eax
is_ordered+80: setne  %al
is_ordered+83: movzbl %al,%eax
is_ordered+86: jmp    0x4014a2 <is_ordered+34>
!}
is_ordered+34: add    $0x18,%esp
is_ordered+37: pop    %ebx
is_ordered+38: ret    
is_ordered+39: mov    %esi,%esi
is_ordered+41: lea    0x0(%edi,%eiz,1),%edi

Vabbé approfondirò per conto mio

M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricorsione in C
13 giu 2020, 13:41
In effetti ...
```
...
is_ordered+73: call   0x401480 <is_ordered>
...
```
C'e' una call che non ci dovrebbe essere.
Non so: me lo hanno insegnato all'univ, e almeno una volta l'ho visto.
Questo al tempo dei dinosauri, pero'

In ogni caso, NON E' una cosa esotica o che mi sono inventato io.
E' una cosa che ti insegnano al corso di linguaggi formali e compilatori.
O, almeno, insegnavano
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Ricorsione in C
13 giu 2020, 14:30
migliorabile ha scritto:
@Nippolo, in generale se un 'char' e' 'signed' o 'unsigned' e' una cosa che dici al compilatore prima di compilare.
Lo so perche' all'alba dei tempi impostavo VisualStudio per avere il char 'unsigned'.
Molto probabilmente di default e' 'signed'.
Ma e' anche probabile che dipenda dal compilatore, quindi non c'e' la risposta definitiva.
Capisco, in ogni caso non mi ero focalizzato più di tanto sulla questione perché in un caso o nell'altro cambiava ben poco rispetto alla tesi a cui volevo giungere.
Alexv ha scritto:
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.
In realtà non c'è alcuna necessità di utilizzare altri argomenti e/o funzioni per evitare di controllare oltre il carattere terminatore di stringa.
Per esempio la versione da me postata scongiurava questa evenienza grazie al meccanismo di valutazione a corto circuito delle espressioni logiche.
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricorsione in C
13 giu 2020, 14:56
Il motivo per cui e' meglio indicare ESPLICITAMENTE anche la dimensione della stringa (e cosi' anche dei vettori, in questo modo si utilizza un approccio STANDARD) e' ""funzionale"" all'identificazione di eventuali bug.

StandardOil

Utente Attivo

Iscritto da: mar, 2019

Messaggi:: 432

Re: Ricorsione in C

13 giu 2020, 19:19

Cià dai... per chiudere il cerchio:

ho dato una "sgrassata" al codice di Alexv, peraltro ottimo, ma secondo me si poteva limare qualcosina


_Bool ordinatar2(char * s)
{
   // versione ricorsiva a puntatori
   if(!s) return 0;  // caso puntatore nullo

   if(!*s) return 1;  // caso stringa finita

   if(*s > *(s + 1)) return 0; // caso stringa decrescente
   // che s+1 sia un puntatore valido che punta "nella" stringa è garantito dal fatto che *s non è il terminatore

   return ordinatar2(s + 1); // caso ricorsione
}

qui si fa tutto con una sola funzione
perché invece di calcolare a parte l'indice e non aggiornare mai il puntatore basta aggiornare il puntatore e non usare indici, si risparmia una variabile


_Bool ordinatar3(char * s)
{
   // versione ricorsiva a indici
   if(!s) return 0;  // caso puntatore nullo

   if(!s[0]) return 1;  // caso stringa finita

   if(s[0] > s[1]) return 0; // caso stringa decrescente

   return ordinatar3(&s[1]); // qui verrebbe bene usare un puntatore,
   // ma volendo la versione a indici serve passare per l'indirizzo
   // del secondo carattere della stringa
}

questa è la sua sorella che usa gli indici invece dei puntatori, notare il macchinoso giro per passare comunque la parte di stringa ancora da esaminare pur non volendo usare esplicitamente l'aritmetica dei puntatori
qui gli indici ci sono, ma non sono variabili, sono costanti scritte


_Bool _ordinatar4(char *s)
{
   // versione ricorsiva a puntatori
   if(!*s) return 1;  // caso stringa finita

   if(*s > *(s + 1)) return 0; // caso stringa decrescente

   return _ordinatar4(s + 1); // caso ricorsione
   // la versione a indici è simile
}
_Bool ordinatar4(char * s)
{
   if(!s) return 0;  // caso puntatore nullo

   // basta controllarlo solo la prima volta, dopo il puntatore
   // è sempre sicuramente valido
   return _ordinatar4(s);
}

qui invece si passa per una funzione preparatoria, che fa effettivamente un lavoro utile: non aggiunge una variabile non strettamente necessaria, ma bensì esclude fin da subito un caso che, se capita, capita solo alla prima chiamata

M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6011
Re: Ricorsione in C
13 giu 2020, 21:50
Non funziona!
O
oregon
Super Famoso
Iscritto da
nov, 2011
Messaggi:
21792
Re: Ricorsione in C
13 giu 2020, 21:56
@migliorabile.... non mi intrometto nella discussione che sto solo leggendo... ma la pianti con tutti questi c'è che dovrebbero essere ce .... ? E povera lingua italiana!

Anche se CE ne faremo una ragione... e non è per capire chi CE l'ha più lungo...
A
Alexv
Molto attivo
Iscritto da
giu, 2018
Messaggi:
646
Re: Ricorsione in C
13 giu 2020, 23:24
StandardOil specifico che se ho usato le quadre non era per risparmiare cicli CPU (che in effetti sembrano aumentare, a giudicare dall'assembly), ma solo per farlo più chiaro.
Comunque nella versione ultima che hai postato, c'è una cosa che non mi torna:
```
 if(*s > *(s + 1)) return 0;
```
Se ti trovi nella penultima posizione, ritornerà sempre 0 perché *(s+1) è uguale a \0.
StandardOil
Utente Attivo
Iscritto da
mar, 2019
Messaggi:
432
Re: Ricorsione in C
13 giu 2020, 23:31
Temo tu abbia ragione
Anzi, ad essere onesto, sono convinto tu abbia ragione

E credo pure che una eventuale correzione al volo sarebbe deleteria

Mi sa che stavolta ho cappellato

Devi accedere o registrarti per scrivere nel forum

43 risposte