Recursión (Puntos extras)

La recursión se basa en expresar el resultado de un problema como operaciones aplicadas sobre una instancia reducida del mismo problema, hasta que se llega a un caso donde el problema queda bien definido.

En terminos mas simples la recursión se realiza cuando una función se llama a si misma, hasta llegar a un caso base.

Algunos ejemplos sobre recursión:

• Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.

• Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

 Ejemplos Básicos en C

 Bueno a continuación dos ejemplos en C sobre la recursión, ya saben cuales son.

Fibonacci

#include <stdio.h>
 
long fibonacci( long n ); 
 int main()
{
   long resultado; 
   long numero;     
   printf( "Introduzca un entero: " );
   scanf( "%ld", &numero);
 
     resultado = fibonacci( numero );
 
     printf( "Fibonacci( %ld ) = %ldn", numero, 

    resultado );
      return 0; 
 
} 
 long fibonacci( long n )
{
      if ( n == 0 || n == 1 ) {
      return n;   }
   else { 
      return fibonacci( n - 1 ) + fibonacci( n - 2 );
   }    } 

Factorial

#include <stdio.h>
 
long factorial( long numero ); 

int main()
{
   int i; 

   for ( i = 0; i <= 10; i++ ) {
      printf( "%2d! = %ldn", i, factorial( i ) );
   }     return 0; 
} 
 long factorial( long numero )
{
     if ( numero <= 1 ) {

       return 1;   } 
   else { 
      return ( numero * factorial( numero - 1 ) );
   }  } 

Referencias:

Recursión
Información Sobre recursión
Ejemplo 1

Ejemplo 2