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