Module: (C++) Recursión


Problem

5/12

Recursión e iteración

Theory Click to read/hide

Recursión e iteración
Para comprender la recursividad, debe comprender la recursividad...
 
Iteración en programación - un pasode un proceso cíclico de procesamiento de datos. 
A menudo, los algoritmos iterativos en el paso actual (iteración) utilizan el resultado de la misma operación o acción calculada en los pasos anteriores.  Un ejemplo de tales cálculos es el cálculo de las relaciones de recurrencia. 
Un ejemplo simple de un valor recursivo es el factorial: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
El cálculo del valor en cada paso (iteración) es \(N=N \cdot i\) .  Al calcular el valor de \(N\), tomamos el valor ya almacenado \(N\).< br />
El factorial de un número también se puede describir usando la fórmula recurrente:
\(\begin{ecuación*} n!= \begin{casos} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casos} \end{ecuación*}\)

Puede notar que esta descripción no es más que una función recursiva.
Aquí, la primera línea (\(n <= 1\)) es el caso base (condición de terminación de recursividad) y la segunda línea es la transición al siguiente paso.  < br />  
Debe entenderse que las llamadas a funciones implican una sobrecarga adicional, por lo que un cálculo factorial no recursivo será un poco más rápido. 

Conclusión: donde puede escribir un programa con un algoritmo iterativo simple, sin recursión, entonces necesita escribir sin recursión. Pero aun así, existe una gran clase de problemas en los que el proceso computacional se implementa solo mediante recursividad.
Por otro lado, los algoritmos recursivos suelen ser más comprensibles.
 

Problem

Defina una función K(n) que devuelva el número de dígitos en un número natural dado n como

\(\begin{ecuación*} K(n) = \begin{casos} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{si n >= 10} \end{casos} \end{ecuación*}\).

Escribe una función recursiva para calcular el número de dígitos en un número natural n usando la proporción anterior.

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++
Función factorial recursiva Algoritmo iterativo
factorial int(int n) { si (n > 1) devuelve n * Factorial(n - 1); de lo contrario devuelve 1; } x = 1; para (i = 2; i <= n; i++) x = x * yo; cout << x;
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!