Module: (C++) Récursivité


Problem

5/12

Récursivité et itération

Theory Click to read/hide

Récursivité et itération
Pour comprendre la récursivité, vous devez comprendre la récursivité...
 
Itération en programmation - une étaped'un processus de traitement de données cyclique. 
Souvent, les algorithmes itératifs à l'étape en cours (itération) utilisent le résultat de la même opération ou action calculée aux étapes précédentes.  Un exemple de tels calculs est le calcul des relations de récurrence. 
Un exemple simple de valeur récursive est la factorielle : \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Le calcul de la valeur à chaque étape (itération) est \(N=N \cdot i\) .  Lors du calcul de la valeur de \(N\), nous prenons la valeur déjà stockée\(N\).< br />
La factorielle d'un nombre peut également être décrite à l'aide de la formule récurrente :
\(\begin{equation*} n != \begin{cases} 1 &\text{n <= 1,}\\ (n-1) ! \cdot n &\text{n > 1.} \end{cas} \end{équation*}\)

Vous remarquerez peut-être que cette description n'est rien de plus qu'une fonction récursive.
Ici, la première ligne (\(n <= 1\)) est le cas de base (condition de terminaison de la récursivité) et la deuxième ligne est la transition vers l'étape suivante.  < br />  
entier Factoriel(int n) { si (n > 1) return n * Factoriel(n - 1); sinon retourner 1 ; }
x = 1 ; pour (i = 2; je <= n; i++) x = x * je ; cout << x ;
Fonction factorielle récursive Algorithme itératif

Il faut comprendre que les appels de fonction impliquent une surcharge supplémentaire, donc un calcul factoriel non récursif sera légèrement plus rapide. 

Conclusion : où vous pouvez écrire un programme avec un algorithme itératif simple, sans récursivité, alors vous devez écrire sans récursivité. Mais encore, il existe une grande classe de problèmes où le processus de calcul est mis en œuvre uniquement par récursivité.
En revanche, les algorithmes récursifs sont souvent plus compréhensibles.
 

Problem

Définissez une fonctionK(n) qui renvoie le nombre de chiffres dans un nombre naturel donnén comme

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

Écrivez une fonction récursive pour calculer le nombre de chiffres dans un nombre naturel n en utilisant le rapport ci-dessus.

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!