Module: (C++) 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 passo successivo.  
 
Funzione fattoriale ricorsiva Algoritmo iterativo
int Fattoriale(int n) { se (n > 1) return n * Fattoriale(n - 1); altrimenti restituisce 1; } x = 1; per (i = 2; i <= n; i++) x = x * io; cout << x;

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 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include<iostream>
using namespace std;

int CountDigit(int n)
{            
  return 1 + CountDigit(n / 10);
}

main()
{
  int n;
  cin >> n;
  cout << CountDigit(n);
}

     

Program check result

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