La programación recursiva... un tema apasionante.
Su origen es anterior a la
programación iterativa y, en algunos contextos, se suele referir a ella como una modalidad de
programación declarativa. ¿por qué? Porque...
¡ es más sencilla !
Consiste en
declarar, no en
programar, la expresión que deseas ( Esta sutil distinción se aprecia con la experiencia...).
An = 2An-1 + 3
A0 = 1
Fíjate que es prácticamente lo mismo que en la expresión matemática.... No hay "variables" (salvo el parámetro), no hay asignaciones, no hay bucles... Casi parece
matemáticas y no
computación...
fun A(in int n) dev int
{
case n==0 : dev 1
case n> 0 : dev 2*A(n-1) + 3
}
La transcripción a lenguaje como C puede quedar:
#include <stdio.h>
unsigned int A(const unsigned int n)
{
if (n==0) return 1;
if (n>0) return (2*A(n-1) + 3);
}
#define MAXIMUM 20
int main(int argc, char *args[])
{
unsigned int n;
for( n=0; n<MAXIMUM ; n++)
printf("A\(%2u\) : %8u\n",n
,A
(n
)); }
La salida da lo siguiente:
A( 0) : 1
A( 1) : 5
A( 2) : 13
A( 3) : 29
A( 4) : 61
A( 5) : 125
A( 6) : 253
A( 7) : 509
A( 8) : 1021
A( 9) : 2045
A(10) : 4093
A(11) : 8189
A(12) : 16381
A(13) : 32765
A(14) : 65533
A(15) : 131069
A(16) : 262141
A(17) : 524285
A(18) : 1048573
A(19) : 2097149
Si quieres una versión más "C-flavour"/NINJA puedes hacer:
unsigned int A(const unsigned int n)
{
return n?(2*A(n-1)+3):1 ;
}
Cuidadito que el paso de mates a C no es gratis... Más allá de A=29, la función desborda los valores de unsigned int....