Recursividad

Recursividad
Una función que se llama a sí misma se denomina recursiva

Utilidad
Cuando la solución de un problema se puede expresar en términos de la resolución de un problema de la mismanaturaleza, aunque de menor complejidad. Sólo tenemos que conocer la solución no recursiva para algún caso sencillo (denominado caso base) y hacer que la división de nuestro problema acabe recurriendo a loscasos base que hayamos definido. Como en las demostraciones por inducción, podemos considerar que “tenemos resuelto” el problema más simple para resolver el problema más complejo (sin tener quedefinir la secuencia exacta de pasos necesarios para resolver el problema).

Funcionamiento
- Se descompone el problema en problemas de menor complejidad (algunos de ellos de la misma naturaleza que elproblema original). - Se resuelve el problema para, al menos, un caso base. - Se compone la solución final a partir de las soluciones parciales que se van obteniendo.

Diseño de algoritmosrecursivos
1. Resolución de problema para los casos base: o Sin emplear recursividad. o Siempre debe existir algún caso base.

2. Solución para el caso general: o Expresión de forma recursiva. o Puedenincluirse pasos adicionales (para combinar las soluciones parciales).

Siempre se debe avanzar hacia un caso base: Las llamadas recursivas simplifican el problema y, en última instancia, los casos basenos sirven para obtener la solución.

int factorial (int n) { int resultado; if (n==0) // Caso base resultado = 1; else // Caso general resultado = n*factorial(n-1); return (resultado); } intpotencia (int base, int exp) { if (exp==0) // Caso base return 1; else // Caso general return base * potencia(base,exp-1); }

Recursividad vs. iteración
Aspectos que hay que considerar al decidir cómoimplementar la solución a un problema (de forma iterativa o de forma recursiva): - La carga computacional (tiempo de CPU y espacio en memoria) asociada a las llamadas recursivas. - La redundancia...