Module: (Java) Sub-rotinas. Recursão.


Problem

5/10

Recursão e iteração

Theory Click to read/hide

Para entender a recursão, você precisa entender a recursão...
 
Iteração na programação — em um sentido amplo — organização do processamento de dados, na qual as ações são repetidas várias vezes, sem levar a chamadas para si mesmas (ao contrário de  %BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Recursão" >Recursões). No sentido estrito — processo de processamento de dados cíclicos em uma etapa. 
Freqüentemente, algoritmos iterativos na etapa atual (iteração) usam o resultado da mesma operação ou ação calculada nas etapas anteriores.  Um exemplo desses cálculos é o cálculo das relações de recorrência. 
Um exemplo simples de valor recursivo é o fatorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\) O cálculo do valor em cada etapa (iteração) é \(N=N \cdot i\) .  Ao calcular o valor de \(N\), tomamos o valor já armazenado \(N\).< br />
O fatorial de um número também pode ser descrito usando a fórmula recorrente:



Você pode perceber que esta descrição nada mais é do que uma função recursiva.
Aqui a primeira linha (\(n <= 1\)) — este é o caso base (condição final da recursão) e a segunda linha é a transição para a próxima etapa. 
 
A função fatorial recursiva ficaria assim Compare o algoritmo para encontrar o fatorial da maneira usual não recursiva
int Fatorial(int n){ se (n > 1) return n * Fatorial(n - 1); caso contrário, retorne 1; } x = 1; para (i = 2; i <= n; i++) x = x * i; printf("%d",x);

Deve ser entendido que as chamadas de função envolvem alguma sobrecarga adicional, portanto, um cálculo fatorial não recursivo será um pouco mais rápido. 
Conclusão: onde você pode escrever um programa com um algoritmo iterativo simples, sem recursão, então você precisa escrever sem recursão. Ainda assim, existe uma grande classe de problemas onde o processo computacional é implementado apenas por recursão.
Por outro lado, algoritmos recursivos costumam ser mais compreensíveis.
 

Problem

 Defina uma função K(n) que retorne o número de dígitos em um determinado número natural n: 


Escreva uma função recursiva para calcular o número de dígitos em um número natural 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!