recursion

ING. EN SISTEMAS COMPUTACIONALES

III Semestre

Tema IV. Recursión

Institu

to d

e E

stu

dio

s S

up

erio

res

del Is

tmo

de T

ehuan

tepec

Docente:

M.I. Blanca Elia Jiménez Guzmán

La recursividad es un concepto

importante en la programación,

muchos algoritmos se pueden

describir mejor en términos de

recursividad.

Las pilas se pueden utilizar para

implementar módulos recursivos.

2M.I. Blanca Elia Jiménez Guzmán


Recursión

• Se refiere a la realización de unmódulo o función, que se llama a símismo n veces.

• Un módulo que contiene unasentencia de llamada a un segundomódulo que puede eventualmentellamar al módulo original.

Se debe cuidar que no se ejecute

indefinidamente:

Que exista un criterio base, por el

que el módulo no se llame a sí

mismo.

Cada vez que el módulo se llame a

sí mismo (directa o

indirectamente), debe estar más

cerca del criterio base.



Se refiere a los algoritmos mal

definidos, que no cumplen con el

criterio base, se llama a sí mismo n

veces y no existe un criterio que

rompa con esa estructura, llamándose

a sí mismo infinitamente.


Un ejemplo típico, para aplicar la

recursividad es:

La Función Factorial.

La función factorial, es el

producto de los enteros positivos

desde 1 hasta n, inclusive, se

llama “n factorial” y normalmente

se denota por n!


Es conveniente definir 0! = 1, de

forma que la función esté definida

para todos los enteros no negativos.

0! = 1

1! = 1

2! = 1 X 2 = 2

3! = 1 X 2 X 3 = 6

4! = 1 X 2 X 3 X 4 = 24


observe que:

4! = 4 X 3!

3! = 3 X 2!

Resulta:

n! = n X (n - 1)!

Esta definición de n! es recursiva, ya que

se refiere a sí misma cuando usa (n – 1)!.

El criterio base, está en función de n = 0,

ya que: 0! = 1, así, la función está bien

definida.

M.I. Blanca Elia Jiménez Guzmán 9

E-mail: [email protected]

“Nuestras dudas son traidoras, y porellas perdemos el bien que confrecuencia pudimos ganar, por miedoa intentarlo”.

William Shakespeare

recursion

Education