Module: (Java) Sous-programmes. Récursivité.


Problem

5/10

Récursivité et itération

Theory Click to read/hide

Pour comprendre la récursivité, vous devez comprendre la récursivité...
 
Itération dans la programmation — au sens large — organisation du traitement des données, dans laquelle les actions sont répétées plusieurs fois, sans conduire à des appels à elles-mêmes (contrairement à Récursions). Au sens étroit — processus de traitement de données cyclique en une étape. 
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 de récurrence 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 :



Vous remarquerez peut-être que cette description n'est rien de plus qu'une fonction récursive.
Ici la première ligne (\(n <= 1\)) — c'est le cas de base (condition de fin de récursivité) et la deuxième ligne est la transition vers l'étape suivante. 
 
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 ; printf("%d",x);
Une fonction factorielle récursive ressemblerait à ceci Comparez l'algorithme pour trouver la factorielle de la manière habituelle non récursive

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éfinir une fonction K(n) qui renvoie le nombre de chiffres d'un nombre naturel donné n : 


Écrivez une fonction récursive pour calculer le nombre de chiffres dans un nombre naturel n.

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
Java
Write the program below 
import java.util.Scanner;
public class Main {

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

public static void main(String[] args) {
     Scanner in = new Scanner(System.in);
     int n;
     n = in.nextInt();
     System.out.println(CountDigit(n));
   }      
}

     

Program check result

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