Tipos de recursión

ESQUEMA GENERAL

{Q($\bar{x}$)}

función f(x: T1) retorna (y: T2) 
    caso
    Bt(x) -> triv(x) 
    Bnt(x) -> c(f(s(x)), x)
    fcaso 
ffunción

{R($\bar{x}, \bar{y}$)}

donde los parámetros formales $\bar{x}$ e $\bar{y}$ han de entenderse como tuplas { $x_1, x_2,...,x_n$} e { $y_1, y_2,...,y_n$} , respectivamente.

TIPOS DE FUNCIONES RECURSIVAS

Según que el elemento sucesor s($\bar{x}$)sea único o no, pueden presentarse los dos tipos de funciones recursivas siguientes:

• Función recursiva lineal o simple: cuando la función recursiva genera A LO SUMO UNA LLAMADA INTERNA por cada llamada externa.

• Función recursiva no lineal o múltiple: cuando genera DOS O MÁS LLAMADAS INTERNAS por cada llamada externa.

Nota.- Si aparecieran varias llamadas recursivas, cada una en una alternativa diferente de una instrucción condicional, la recursividad seguiría siendo lineal ya que, en tiempo de ejecución, las alternativas son mutuamente excluyentes y a lo sumo se produciría una invocación.

EJEMPLO DE FUNCIÓN RECURSIVA LINEAL O SIMPLE

$Q \equiv a \geq0 \wedge n \geq0$

Funcion POTENCIA (a:entero, n:entero) retorna (p:entero) 
    si n = 0 entonces retorna 1
    sino retorna POTENCIA(a, n-1) * a
    fcaso 
ffunción

$R \equiv${$p = a^{n}$}

EJEMPLO DE FUNCIÓN RECURSIVA NO LINEAL O MÚLTIPLE

{$n \geq0$}

Funcion POTENCIA3 (a:entero, n:entero) retorna (p:entero) 
    caso
        n = 0 -> 1
        n = 1 -> 3
        n > 1 -> 2 *POTENCIA3(n-1) + 3 * POTENCIA3(n-1)
    fcaso 
ffunción

{$f \equiv$$3^{n}$}

EJEMPLO DE FUNCIÓN RECURSIVA LINEAL O SIMPLE

{$a >0 \wedge b>0$}

Funcion Maximo_Comun_Divisor (a,b:entero) retorna (g:entero) 
    caso
        a = b -> a
        a > b -> Maximo_Comun_Divisor(a-b, b)
        a < b -> Maximo_Comun_Divisor(a, b-a)
    fcaso 
ffunción

{$g=$$mcd(a,b)$}

TIPOS DE FUNCIONES RECURSIVAS

Según que el comportamiento de la función c (función de combinación) pueden presentarse los dos tipos de funciones recursivas siguientes:

• Función recursiva no final o no de cola: cuando la función c es necesaria, esto es, f(̅$\bar{x}$) = c(f(s(̅$\bar{x}$)),$\bar{x}$)
• Función recursiva final o de cola: cuando la función c no es necesaria, esto es, f(̅ $\bar{x}$) = f(s($\bar{x}$))

FUNCIÓN RECURSIVA NO FINAL O NO DE COLA

Cuando la función c SÍ es necesaria

función f(x: T1) retorna (y: T2) 
    caso
    Bt(x) -> triv(x) 
    Bnt(x) -> , x)
    fcaso 
ffunción

FUNCIÓN RECURSIVA FINAL O DE COLA

Cuando la función c NO es necesaria

función f(x: T1) retorna (y: T2) 
    caso
    Bt(x) -> triv(x) 
    Bnt(x) -> f(s(x), x)
    fcaso 
ffunción

EJEMPLO DE FUNCIÓN RECURSIVA NO FINAL O NO DE COLA

$Q \equiv a \geq0 \wedge n \geq0$

Funcion POTENCIA (a:entero, n:entero) retorna (p:entero) 
    si n = 0 entonces retorna 1
    sino retorna POTENCIA(a, n-1) * a
    fcaso 
ffunción

$R \equiv${$p = a^{n}$}

EJEMPLO DE FUNCIÓN RECURSIVA FINAL O DE COLA

{$a >0 \wedge b>0$}

Funcion Maximo_Comun_Divisor (a,b:entero) retorna (g:entero) 
    caso
        a = b -> a
        a > b -> Maximo_Comun_Divisor(a-b, b)
        a < b -> Maximo_Comun_Divisor(a, b-a)
    fcaso 
ffunción

{$g=$$mcd(a,b)$}

EJEMPLO DE FUNCIÓN RECURSIVA NO FINAL O NO DE COLA

{$n \geq0$}

Funcion POTENCIA3 (a:entero, n:entero) retorna (p:entero) 
    caso
        n = 0 -> 1
        n = 1 -> 3
        n > 1 -> 2 *POTENCIA3(n-1) + 3 * POTENCIA3(n-1)
    fcaso 
ffunción

{$f \equiv$$3^{n}$}