Edición importante, provocada por una pregunta de seguimiento en los comentarios: mi respuesta anterior aparece a continuación.
Hay dos significados muy distintos de la frase “función recursiva” que, obviamente, se confunden en esta pregunta. Depende de si lo miras con gafas de informática o con gafas de matemático.
Informática de bajo nivel:
- ¿Es el código realmente ilegible sin los caracteres de espacio 'innecesarios'?
- Cómo ser un programador perfecto paso a paso
- Recientemente he entregado mis tableros (12) y quiero hacer una mecánica BTech. Espero 85% en tableros, pero estoy seguro de que no romperé el avance de IIT. ¿Qué debo hacer, dejar un año y tomar clases de IIT o elegir la universidad solo este año? ¿Es seguro dejar caer un año?
- Para los usuarios, ¿se está volviendo Facebook más valioso, útil y digno de más tiempo invertido o menos? ¿Por qué? ¿Hay alguna evidencia de Facebook de que la Ley de Metcalfe es cierta (para n usuarios, el valor de la red aumenta en nxn)?
- Un niño que sube una escalera con n escalones puede subir 1, 2 o 3 escalones a la vez. ¿De cuántas maneras puede llegar el niño a la cima?
En informática, cuando las personas dicen “función”, normalmente se refieren a una parte de un programa que opera en un conjunto de entradas y luego produce una salida. Echa un vistazo a estas dos funciones:
int factorial (int n) {
if (n == 0) devuelve 1;
retorno n * factorial (n-1);
}
versus:
int factorial (int n) {
int resultado = 1;
para (int i = 2; i <= n; i ++) {
resultado * = i;
}
resultado de retorno;
}
Muchos informáticos llamarían a la primera función una “función recursiva”, porque se define en términos de llamadas a sí mismas , y llamarían a la segunda función una “función iterativa”, porque solo usa un bucle for, que es una iteración construir.
Si interpreta “recursivo” e “iterativo” de esta manera, como hice en mi respuesta original y creo que la interpretación utilizada en esta pregunta, entonces es realmente cierto que todas las funciones recursivas también pueden implementarse de manera iterativa; de hecho, en última instancia, todas las funciones recursivas se traducen en implementaciones iterativas en algún momento, porque las CPU de la mayoría de las computadoras modernas no tienen construcciones de recursión incorporadas.
Matemática / informática teórica:
Ahora un matemático podría decir: ¡las dos funciones anteriores no son en realidad dos funciones distintas en absoluto! Producen la misma salida en todas las entradas, por lo que estos dos programas son dos implementaciones distintas de la misma función. No tiene sentido llamar a la función recursiva, porque como acabamos de ver, ¡la misma función tiene una definición recursiva y una iterativa!
Aún así, en informática teórica, las personas también pueden hablar sobre funciones recursivas , pero si lo hacen, significan algo bastante diferente. En realidad, no soy fanático de cómo se llama esto, precisamente porque invita a esta confusión.
Esta segunda interpretación de la palabra “recursivo” entra en juego cuando las personas intentan clasificar las funciones en una jerarquía de clases cada vez más ricas. (Esto se llama la “jerarquía de idiomas Chomsky”). Una clase muy importante es la clase de funciones recursivas ; de hecho, este nombre es tan confuso que muchos autores ahora llaman a este grupo las funciones computables , lo que es mucho menos probable que cause confusión. Una función es computable (“recursiva”) si existe algún algoritmo informático que la implemente, produciendo una salida correcta para cualquier entrada.
La función de Ackermann es un ejemplo de una función que es computable (“recursiva”), porque en teoría hay un programa de computadora que calcula el valor correcto para cualquier entrada, ¡incluso si ese programa puede ser un poco lento en la práctica!
Sin embargo, en el video vinculado en los comentarios, el tipo dice que la función de Ackermann no está en la clase de “funciones recursivas primitivas”, que es un subconjunto de las funciones computables.
Vieja respuesta:
Todos los problemas recursivos se pueden resolver de forma iterativa, haciendo explícita la pila de llamadas.
Piénselo de esta manera: la CPU no tiene instrucciones para la recursividad. El código de la máquina es iterativo.
