Divide y vencerás
Otra técnica común usada en el diseño de algoritmos es el de “divide y vencerás” y que consta de dos partes:
– Dividir: los problemas más pequeños se resuelven recursivamente (excepto, por supuesto, los casos base).
– Vencer: la solución del problema original se forma entonces a partir de las soluciones de los subproblemas.
Las rutinas en las cuales el texto contiene al menos dos llamadas recursivas se denominan algoritmos de divide y vencerás, no así las rutinas cuyo texto sólo contiene una llamada recursiva.
La idea de la técnica divide y vencerás es dividir un problema en subproblemas del mismo tipo y aproximadamente todos ellos del mismo tamaño, resolver los subproblemas recursivamente y, finalmente, combinar la solución de los subproblemas para dar una solución al problema original. La recursión finaliza cuando el problema es pequeño y la solución es fácil de construir directamente.
Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM
