Taller recursividad

Vista previa del material en texto

TALLER RECURSIVIDAD
La idea básica detrás de los algoritmos recursivos es:
Para resolver un problema, resuelve un subproblema que sea una instancia más pequeña del mismo problema, y después usa la solución de esa instancia más pequeña para resolver el problema original.
Para que un algoritmo recursivo funcione, los subproblemas más pequeños eventualmente deben llegar al caso base. Cuando calculamos n!, los subproblemas se hacen más y más pequeños hasta que calculamos 0!. Debes asegurarte de que, eventualmente, llegues al caso base.
Podemos extraer la idea de la recursión en dos reglas sencillas:
Cada llamada recursiva debe ser sobre una instancia más pequeña del mismo problema, es decir, un subproblema más pequeño.
Las llamadas recursivas eventualmente deben alcanzar un caso base, el cual se resuelve sin más recursividad.
1. Calcular el máximo común divisor de dos números enteros puedo aplicar el algoritmo de Euclides, que consiste en ir restando el más pequeño del más grande hasta que queden dos números iguales, que serán el máximo común divisor de los dos números.
Por ejemplo, si comenzamos con el par de números 412 y 184, tendríamos:
	412
	228
	44
	44
	44
	44
	44
	36
	28
	20
	12
	8
	4
	184
	184
	184
	140
	96
	52
	8
	8
	8
	8
	8
	4
	4
Es decir, m.c.d.(412, 184) = 4
2. Diseñar un método recursivo tal que dado un vector de números enteros retorne la suma de sus elementos. Para poder hacer recursividad, usaremos un índice que indique el trozo de vector a sumar en cada llamada. Es decir, el método a diseñar tendrá la forma:
public int sum(int[] elems,int pos){
 ¿?
}