Imprimir Página - Funcion recursiva

Título: Funcion recursiva
Publicado por: Kinamox en 7 Abril 2018, 02:25 am

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.

Título: Re: Funcion recursiva
Publicado por: Serapis en 7 Abril 2018, 03:32 am

Código:

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:

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

Título: Re: Funcion recursiva
Publicado por: dijsktra en 8 Abril 2018, 11:50 am

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

Cita de: Kinamox en 7 Abril 2018, 02:25 am

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:

  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

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

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

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

Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: Kinamox en 7 Abril 2018, 02:25 am