Introducción

El capítulo «Recursividad» empezó a mostrar cómo definir un módulo que realiza un tratamiento repetido, usando sus propios servicios. Nos hemos dado cuenta de que la realización de un módulo de este tipo expresa una definición, en el sentido matemático del término, antes que una serie de transformaciones para aplicar a los datos. En el capítulo «Iteración» ha estudiado con detalle cómo razonar un problema que transforma los datos mediante un tratamiento repetido. Este capítulo es corto y realiza una síntesis de los tratamientos repetidos comparando los dos métodos.

La sección «Recordamos la recursividad» retoma el capítulo anterior representando varios ejemplos elementales pero significativos de recursividad simple. La sección «¿Recursividad o iteración?» da algunos elementos para comparar recursividad e iteración y pone de manifiesto los motivos por los que se prefiere la iteración a la recursividad para la programación de tratamientos repetidos. Por último, la sección «Ejercicios», propone algunas actividades para usar los elementos presentados. El capítulo termina con un resumen.

Recordamos la recursividad

Un algoritmo recursivo expresa una definición en lugar de decir cómo realizar las transformaciones con los datos. Vamos a volver a ver este punto con un ejemplo básico, que ya empezamos a estudiar en el capítulo «Recursividad».

1. Primer ejemplo

Para empezar, vamos a recordar el problema.

Un carácter es un número entero positivo o nulo. Más adelante, un carácter se confunde con su código numérico. El dominio de los valores de un número entero de este tipo no se precisa más. Podemos pensar en él suponiendo, por ejemplo, que el dominio depende de la máquina utilizada. El tipo de datos CARÁCTER permite definir una variable de tipo carácter.

Uno de estos caracteres es un código particular. Se designa por FIN_CA. Este carácter nunca es un carácter significativo en una cadena. Solo se utiliza para marcar el final de una cadena. Así, todos los datos de tipo CADENA contienen, como último carácter, el de código FIN_CH que marca el final. Los caracteres de una cadena están numerados secuencialmente a partir de 1 para el primero.

El accesor ítem, que ya hemos definido antes, está disponible en el repertorio de instrucciones. Es una función que toma como entrada una cadena de caracteres bien formada, es decir, terminada por FIN_CH, y un número entero natural posición. Devuelve el carácter de la cadena que ocupa la posición dada, como en los capítulos anteriores. Igualmente, también están disponibles las funciones primero y fin definidas en los capítulos anteriores. La función primero devuelve una copia del primer carácter de la cadena que recibe como parámetro. La función fin devuelve una copia de la cadena que recibe como parámetro, pero privada de su primer carácter.

Nos interesa el cálculo del número de caracteres de una cadena. El carácter FIN_CA no se cuenta.

Entonces, el problema es definir un algoritmo que devuelve el número de caracteres que componen una cadena bien formada. Hay muchas maneras de resolver este problema.

La manera más sencilla e inmediata consiste en dar una definición de la longitud de la cadena. Como la cadena está bien formada por hipótesis, estamos seguros de...

¿Recursividad o iteración?

Para comprender la diferencia esencial que hace preferir un algoritmo iterativo a un algoritmo recursivo, estudiamos el «funcionamiento» de las dos versiones del cálculo de la longitud de una cadena de caracteres, como se ha presentado en la sección anterior.

Las etapas del cálculo recursivo son las siguientes:

(i)  : 'abc' ≠ CADENA_VACÍA => longitud('abc') = 1 + longitud('bc'); 
(ii) : 'bc'  ≠ CADENA_VACÍA => longitud('bc')  = 1 + longitud('c') ; 
(iii): 'c'   ≠ CADENA_VACÍA => longitud('c')   = 1 + longitud('')  ; 
(iv) : ''    = CADENA_VACÍA => longitud('')    = 0 
 
(j)  : longitud('')   = 0  => longitud('c')    = 1 + 0 = 1; 
(jj) : longitud('c')  = 1  => longitud('bc')   = 1 + 1 = 2; 
(jjj): longitud('bc') = 2  => longitud('abc')  = 1 + 2 = 3

Los elementos sucesivos del cálculo, es decir, las cadenas de caracteres en las que opera el algoritmo, están colocadas en espera del resultado intermedio para terminar el cálculo. El cálculo de la longitud de ’abc’ está colocado en espera del resultado de la longitud de ’bc’. Este cálculo se coloca en espera del resultado del cálculo de la longitud de ’c’. Este último cálculo se coloca en espera...

Ejercicios

Ejercicio resuelto 1: Función factorial

Transformar el algoritmo de la función factorial estudiada en el capítulo «Recursividad» para hacer un algoritmo de recursividad terminal.

Solución

Es suficiente con usar un acumulador inicializado en 1 porque factorial(0) = factorial(1) = 1.

Algoritmo 3: Función factorial (recursividad terminal)

Algoritmo factorial  
    # n!  
  
Entrada 
    n: ENTERO 
    ACM: ENTERO  
  
precondición 
    n ≥ 0  
  
realización  
    si 
        n < 2  
    entonces  
        Resultado  ACM  
    si no   
        Resultado  factorial(n - 1, ACM x n)  
    fin si  
  
poscondición  
    Resultado = n!  
  
fin factorial

La función se utiliza así:

k  factorial(10, 1) # calcula 10! con ACM inicializado a 1

Ejercicio resuelto 2: Función pertenece

1. Escribir una función pertenece que devuelve VERDADERO si y solo si el carácter que recibe como segundo parámetro compone la cadena que recibe como primer parámetro.

2. ¿La solución propuesta es una recursividad terminal?

Solución

El resultado es evidentemente FALSO cuando la cadena de caracteres está vacía:

ca = CADENA_VACÍA => Resultado = FALSO

El resultado es VERDADERO si el carácter buscado es el primero de la cadena cuando no está vacía:

ca ≠ CADENA_VACÍA => Resultado = (primero(ca) = car) ...

Cuando no es el primero, el resultado es VERDADERO si el carácter pertenece al resto de la cadena:

... o si no Resultado = pertenece(car, fin(ca)))

Entonces, el algoritmo solicitado es:

Algoritmo 4: Función pertenece

Algoritmo pertenece, infijo   
    # ¿car pertenece a ca?  
  
Entrada 
    car: CARÁCTER 
    ca:...

Resumen

Este capítulo es una introducción corta a los problemas provocados por la recursividad. Hemos visto algunos elementos que nos permiten ser conscientes de los inconvenientes de la recursividad, pero también de las ventajas incomparables que presentan estas soluciones, especialmente dentro de la potencia de expresividad que permiten. Hemos introducido la recursividad terminal y definido los motivos que hacen que se puedan usar estas soluciones, en programación, sin grandes inconvenientes con un compilador de lenguaje moderno. También sería necesario mostrar cómo transformar los algoritmos recursivos en algoritmos iterativos y cómo probar un algoritmo recursivo, pero estos problemas sobrepasan el marco de esta iniciación.