Recursividad En Java

Recursividad
Es la técnica de definir un proceso en términos de
si mismo.
Por ejemplo, la definición de una “Lista”:

Recursividad

Una LISTA es:

Franco Guidi Polanco

número
número comaLISTA

La definición anterior caracteriza como Lista cada
una de las siguientes secuencias de números:

Escuela de Ingeniería Industrial
Pontificia Universidad Católica de Valparaíso, Chilefguidi@ucv.cl

• 23, 12, 23, 4
•7
• 1, 6
Actualización: 03 de octubre de 2005
Franco Guidi Polanco (PUCV-EII)

Recursividad

2

Ejemplo de función recursiva

Otro ejemplo de recursividad:el factorial de un
número.

factorial( x ) =

3/9/2007

Implementación de la función Factorial:
public class Utiles {
public static int factorial(int n){
if( n > 0 )
return n*factorial( n-1);
else
return 1;
}
}

x * factorial( x-1 ) si x > 0
1
si x = 0

public class Ejemplo {
public static void main(String[] arg){
System.out.println(Utiles.factorial( 4 ));
}
}
FrancoGuidi Polanco (PUCV-EII)

3/9/2007

3

Franco Guidi Polanco (PUCV-EII)

3/9/2007

4

Ejemplo de función recursiva (cont.)
...
public static int factorial(int n){
if( n > 0 )
returnn*factorial(n-1);
else
return 1;
}
...

Ejemplo de función recursiva (cont.)
...
public static int factorial(int n){
if( n > 0 )
return n*factorial(n-1);
else
return 1;
}
...

Stack deinvocaciones
del método factorial

n=0

return 1

n=1

return 1*factorial(0)

n=2

return 2*factorial(1)

Stack de invocaciones
del método factorial

return 1

n=1

return1*factorial(0)
return 2*factorial(1)

n=3

return 3*factorial(2)

n=4

factorial=1

n=0

n=2

factorial=1

return 4*factorial(3)

factorial=2
n=3

return 3*factorial(2)
factorial=6

n=4return 4*factorial(3)
factorial=24
...
r=Utiles.factorial(4);
...

...
r=Utiles.factorial(4);
...
Franco Guidi Polanco (PUCV-EII)

3/9/2007

5

Recursividad y condición de término...