RECURSIVIDAD 2

- 103 -

11. RECURSIVIDAD 2 En este tema continuamos el repaso de las llamadas recursivas con algunos ejemplos y ejercicios adicionales. 11.1. EJEMPLOS/EJERCICIOS 1. Elabore y pruebe una función recursiva que calcule la potencia entera de un número real. Desde el punto de vista recursivo el problema se resuelve multiplicando por “x” la potencia previa, es decir:

x n =x n−1⋅x Y dado que cualquier número elevado a 1 es el mismo número, esa puede ser la condición de finalización:

x 0=1 No obstante, esta solución aunque es correcta, no es eficiente. Por ejemplo para calcular 3.452500000, se requieren ¡2 millones quinientas mil llamadas recursivas! e igual número de multiplicaciones. Una solución más eficiente se consigue tomando en cuenta que el valor de xn es igual a: n 2 2

( ) si n es par x =( x ) ⋅x si n es impar n

x= x

n

n 2 2

Así por ejemplo el valor de x4561 puede ser calculado con: x4561 = (x(4561-1)/2)2 * x = (x2280)2 * x Para calcular x2280 se aplica el mismo procedimiento: x2280 = (x2280/2)2 = (x1140)2 Prosiguiendo de esta manera los siguientes cálculos serían: x1140 = (x1140/2)2 = (x570)2 x570 = (x570/2)2 = (x285)2 x285 = (x(285-1)/2)2 * x = (x142)2 * x x142 = (x142/2)2 = (x71)2 x71 = (x71/2)2 * x = (x35)2 * x x35 = (x(35-1)/2)2 * x = (x17)2 * x x17 = (x(17-1)/2)2 * x = (x8)2 * x x8 = (x8/2)2 = (x4)2 x4 = (x4/2)2 = (x2)2 x2 = (x2/2)2 = (x1)2 x1 = x En consecuencia, aplicando este procedimiento se requieren 13 repeticio-

- 104 -

Hernán Peñaranda V.

nes y 18 multiplicaciones (en lugar de ¡4561 repeticiones y 4561 multiplicaciones!). Como se puede observar este planteamiento es recursivo y por ello la forma “natural” de resolverlo es con dicha propiedad. Como se sabe, para completar el planteamiento recursivo se requiere una condición de finalización y dado que x0 es 1, la condición de finalización puede ser: cuando “n” es cero el resultado es 1, o dado que x 1 es x, la condición de finalización también puede ser: cuando “n” es 1 el resultado es “x”. El algoritmo que resuelve el problema, empleando la primera condición de finalización es: potr: Potencia entera “n” de un número real “x”. recibir x, n [else]

[n=1]

[n impar]

[else] devolver potr(x,cociente(n/2))2

devolver potr(x,cociente(n/2))2 * x

devolver x

Con este algoritmos está resuelto el problema desde el punto de vista recursivo, sin embargo, existen muchos casos que no han sido tomados en cuenta tales como cuando la base es 1 (caso en el que la solución es siempre 1), o cuando la base es cero (en cuyo caso la solución es 0) o cuando la potencia es negativa (siendo la solución la inversa del valor calculado), o cuando la base y la potencia son cero (resultado es indefinido) etc., etc. Como ya se vio en el tema anterior, todos estos casos deben ser analizados y tratados en otro módulo no recursivo. Se recalca, sin embargo, que el problema en sí ya ha sido resuelto en el módulo recursivo. El algoritmo de dicho módulo es el siguiente: pote: Potencia entera “n” de un número real “x”. recibir x, n

resultado indefinido [(x=0) y (n0) ] [(x=1) o (n=0)]

[(x=-1) y (n es par )] [(x=-1) y (n es impar) ] [nn; } void mostrarResultado(long double x, int n){ try { coutB; C->B; A->C; B->A; C->B; C->A; B->A; B->C; A->C; A->B; C->B; A->C; Número de aros a mover (0 para salir)? 7 Los movimientos necesarios son: A->C; A->B; C->B; A->C; B->A; B->C; A->C; B->A; C->B; A->C; A->B; C->B; A->C; B->A; C->B; C->A; B->A; B->C; A->C; A->B; C->B; A->C; A->B; C->B; C->A; B->A; C->B; A->C; B->A; B->C; A->C; B->A; C->B; C->A; B->A; C->B; A->C; B->A; B->C; A->C; A->B; C->B; A->C; A->B; C->B; A->C; B->A; B->C; A->C; B->A; B->C; A->C; A->B; C->B; A->C; B->A; C->B; C->A; B->A; C->B; A->C; A->B; C->B; A->C; B->A; C->B; C->A; B->A; B->C; A->C; B->A; B->C; A->C; A->B; C->B; C->A; B->A; C->B; A->C; B->A; B->C; A->C; B->A; C->B; A->C; A->B; C->B; A->C; B->A; B->C; A->C; Número de aros a mover (0 para salir)? 0 ¡Error! El número de aros debe ser > 0.

A->B; C->B; C->A; B->C; A->C; B->A; A->C; B->A; B->C;

A->B; B->C; A->C; A->B; C->B; C->A; B->A; B->C; C->A; A->B; C->B; C->A;

C->B; A->C; B->A; C->B; A->C; B->A; C->B; A->C; B->A; C->B; A->C; B->A;

C->A; B->A; B->C; C->A; A->B; C->B; C->A; B->A; B->C; A->C; A->B; B->C;

Como se puede observar, el número de movimientos necesarios incrementa geométricamente con el número de aros, así por ejemplo, para 20 aros se requiere más de un millón de movimientos (haga la prueba). El código equivalente en Javascript es: function hanoir(n,a,c,b){ if (n>0) return hanoir(n-1,a,b,c)+a+"->"+c+"; "+hanoir(n-1,b,c,a); else return ""; } function hanoi(n,a,c,b){ n=parseInt(n); if (n