Funcion recursiva

[Kinamox]

Buenas, alguien de buen corazón podría darme una idea de como hacer esta funcion recursiva:

An = 2An-1 + 3
A0 = 1

[las que no son negritas son sub-indice]

que corresponde a la sucesión {1,5,13,29,61..}.

por favor, necesito hacer el codigo y no encuentro donde basarme.Les agradezco
saludos.

[Serapis]

Código [Seleccionar] Expandir


entero = funcion Recursion(entero Valor, byte veces, byte MaxVeces)
   Veces +=1

   Si (veces < MaxVeces)
       valor = ((2 * (valor -1))  + 3)
       devolver Recursion(valor, veces, maxveces)
   fin si

   devolver valor
fin funcion

p.d.: se me escapó el mensaje sin los comentarios pertinentes:

Efectivamente valor inicialmente podría ser 1, como señalas en A0=1 (nunca 0).
el subíndice 'n', sería 'veces' y MaxVeces, es limitar la recursion a un numero 'n' dado.
...es fácil transformarlo en que veces sea maxveces y acabe cuando llegue a 0, en ese caso decrementando veces... haciendo así innecesario el parámetro 'maxVeces'.

Te invito a hacer esa ligera modificación... una vez entiendas su funcinamiento.

p.d. 2:
Notas que (iterando) la serie puedes resumirla así mejor:

Código [Seleccionar] Expandir


v0 = 2
n0 = 1
veces = ?  // un número que tu mismo pongas...

bucle para k desde 1 a veces  //el ciclo 0, tiene los valores asignados antes del bucle.
   v = 2v
   n =  (n + v)
siguiente en bucle

Así 'v' va tomando valores: 2, 4, 8, 16,  32 ...
Mientras 'n' toma valores: 1, 1+4, 5+8, 13+16, 29+32...

[dijsktra]

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...

Código [Seleccionar] Expandir

 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:

Código (c) [Seleccionar] Expandir

#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:

Código [Seleccionar] Expandir

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:

Código (c) [Seleccionar] Expandir

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....