Module: (C++) 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.  < br />  
Função fatorial recursiva Algoritmo iterativo
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; cout << 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 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 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!