Module: (Python) Subroutine. ricorsione


Problem

5/12

Ricorsione e iterazione

Theory Click to read/hide

Ricorsione e iterazione
Per capire la ricorsione, devi capire la ricorsione...
 
Iterazione nella programmazione: una fasedi un processo ciclico di elaborazione dei dati. 
Spesso gli algoritmi iterativi nella fase corrente (iterazione) utilizzano il risultato della stessa operazione o azione calcolata nelle fasi precedenti.  Un esempio di tali calcoli è il calcolo delle relazioni di ricorrenza. 
Un semplice esempio di valore ricorsivo è il fattoriale: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Il calcolo del valore ad ogni passo (iterazione) è \(N=N \cdot i\) .  Quando calcoliamo il valore di \(N\), prendiamo il valore già memorizzato \(N\).

Il fattoriale di un numero può anche essere descritto usando la formula ricorrente:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casi} \end{equazione*}\)

Potresti notare che questa descrizione non è altro che una funzione ricorsiva.
Qui la prima riga (\(n <= 1\)) è il caso base (condizione di terminazione della ricorsione) e la seconda riga è la transizione al passaggio successivo.  
Funzione fattoriale ricorsiva Algoritmo iterativo
def Fattoriale(n): se n > 1: return n * Fattoriale(n - 1) altro:   ritorna 1 x=1 per i nell'intervallo(1, n + 1): x = x * io;

Dovrebbe essere chiaro che le chiamate di funzione comportano un sovraccarico aggiuntivo, quindi un calcolo fattoriale non ricorsivo sarà leggermente più veloce. 

Conclusione: dove puoi scrivere un programma con un semplice algoritmo iterativo, senza ricorsione, allora devi scrivere senza ricorsione. Tuttavia, esiste un'ampia classe di problemi in cui il processo computazionale è implementato solo mediante ricorsione.
D'altra parte, gli algoritmi ricorsivi sono spesso più comprensibili.
 

Problem

Definisci una funzione K(n) che restituisce il numero di cifre in un dato numero naturale n come

\(\begin{equation*} K(n) = \begin{cases} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{if n >= 10} \end{casi} \end{equazione*}\).

Scrivi una funzione ricorsiva per calcolare il numero di cifre in un numero naturale n usando il rapporto sopra.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
Write the program below 
def CountDigit(n):          
        return 1 + CountDigit(n//10)
        
n = int(input())
print(CountDigit(n))

     

Program check result

To check the solution of the problem, you need to register or log in!