Module: (Python) Sub-rotinas. recursão


Problem

5/12

Recursão e iteração

Theory Click to read/hide

Recursão e iteração
Para entender a recursão, você precisa entender a recursão...
 
Iteração na programação - uma etapade um processo cíclico de processamento de dados. 
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:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casos} \end{equação*}\)

Você pode perceber que esta descrição nada mais é do que uma função recursiva.
Aqui, a primeira linha (\(n <= 1\)) é o caso base (condição de término da recursão) e a segunda linha é a transição para a próxima etapa.  
Função fatorial recursiva Algoritmo iterativo
def Fatorial(n): se n > 1: return n * fatorial(n - 1) outro:   retornar 1 x=1 para i no intervalo (1, n + 1): x = x * i;

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 retorna o número de dígitos em um determinado número natural n como

\(\begin{equação*} K(n) = \begin{cases} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{if n >= 10} \end{casos} \end{equação*}\).

Escreva uma função recursiva para calcular o número de dígitos em um número natural n usando a proporção acima.

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!