Recursividad

Departamento de Lenguajes y Ciencias de la Computación

3
Contenido
1. Concepto de recursividad. 3. Uso de la recursividad. 4. Ejemplos.

Recursividad_________________________________________________________________________________________

2. Funcionamiento de la recursividad.

Diseño de Algoritmos. J.L.Leiva O.

Página 1

Departamento de Lenguajes y Ciencias de la Computación1.- Concepto de recursividad.
• La recursividad es una técnica de programación muy potente que puede ser utilizada en lugar de la iteración. • Permite diseñar algoritmos recursivos que dansoluciones elegantes y simples, y generalmente bien estructuradas y modulares, a problemas de gran complejidad. • ¿En qué consiste realmente la recursividad?. Es una técnica que nos permite que un algoritmose invoque a sí mismo para resolver una "versión más pequeña" del problema original que le fue encomendado. ALGORITMO T(...) .... INICIO .... T(...) .... FIN EJEMPLOS. 1. Factorial. En matemáticas esfrecuente definir un concepto en función del proceso usado para generarlo. Por ejemplo, una descripción matemática de n! es: n! = 1 n⋅(n-1) ⋅....⋅1 si n = 0 si n > 0 void f_rec(...) … { … f_rec(…) …}

También se puede definir de forma más sencilla: n! = 1 n⋅(n-1)! si n = 0 si n > 0

Esta segunda definición es recursiva, puesto que expresamos la función factorial en términos de sí misma. Apartir de esta definición, es fácil obtener un algoritmo recursivo para calcular el factorial de un número natural n. ALGORITMO FactorialR(n:N): N VARIABLES fact:N INICIO SI n= 0 ENTONCES fact :=1 ENOTRO CASO fact := n*FactorialR(n-1) Diseño de Algoritmos. J.L.Leiva O. Página 2

Departamento de Lenguajes y Ciencias de la Computación

FINSI DEVOLVER fact FIN En C++: int Factorial(int n){ intfact; if (n==0) fact=1; else fact=n*Factorial(n-1); return(fact)

}

De esta función podemos sacar varias conclusiones: 1. 2. 3. El subprograma se invoca a sí mismo (esto es lo que lo convierte en...