2005/06 – Fase scolastica – 08

di

Si consideri la seguente funzione A()

Function B(n: Integer): Integer; Forward;
Function A(n: Integer): Integer;
Begin
   If(n > 1) Then
      A:=n*B(n+1)
   Else
      A:=1
End;
Function B(n: Integer): Integer;
Begin
   If(n > 1) Then
      B:=(n-1)*A(n-2)
   Else
      B:=1
End;

Indicare quali sono i valori restituiti dalle invocazioni A(1), A(2), A(3), A(4), A(5).

Risposte:

  1. 1, 4, 24, 192, 1920
  2. 1, 4, 36, 576, 14400
  3. 1, 4, 16, 256, 65536
  4. nessuna delle precedenti.

Soluzione: B.

Soluzione

Tratta da: Materiale didattico 2008

Esempio di funzioni mutuamente ricorsive.
Nell’eseguire la traccia delle funzioni si tenga conto che le funzioni sono ricorsive solo per valori maggiori di 1.
Quindi A(1) darà sempre 1.

Durante il secondo ciclo di traccia si noterà che la chiamata della funzione A(n-2) invocata dalla funzione B è identica alla chiamata precedente come da esemplificazione che segue:

  • A(1)=1
  • A(2): richiama B(3) che richiama A(1)
  • A(3): richiama B(4) che richiama A(2)
  • A(4): richiama B(5) che richiama A(3)
  • A(5): richiama B(6) che richiama A(4).

Quindi il risultato della chiamata di A da parte di B è il risultato della chiamata precedente di A.
Pertanto la semplificazione della funzione è:

A(n) = n*n*risultato chiamata precedente

Esempio:

A(4) = 4*4*A(3) = 4*4*36 = 576.