Concepto de recursión

Es el acto de una función llamándose a sí misma. La recursión. es utilizada para resolver problemas que contienen subproblemas más pequeños. Una función recursiva puede recibir 2 entradas: un caso base (finaliza la recursión) o un un caso recursivo (continúa la recursión).

Esquema:

1. El subprograma se invoca a sí mismo (esto es lo que lo convierte en recursivo).
2. Cada llamada recursiva se hace con un parámetro de menor valor que el de la anterior llamada. Así, cada vez se está invocando a otro problema idéntico pero de menor tamaño.
3. Existe un caso especial en el que se actúa de forma diferente, esto es, ya no se utiliza la recursividad. Lo importante es que la forma en la que el tamaño del problema disminuye asegura que se llegará a este caso especial o caso base. Esto es necesario, porque de lo contrario el programa estaría ejecutándose indefinidamente

Ejemplo: calcular el factorial de un número.

División y conquista

Una técnica que usa la recursión para resolver problemas, también la llaman Dividir y Conquistar.

1. Dividir: dividir el problema en varios sub-problemas iguales de tamaño N/b.
2. Resolver: cada uno de los subproblemas elegidos de manera recursiva.
3. Conquistar: Combinar las sub-soluciones.

Ejemplo: búsqueda binaria