Tarea 3 - Tipos de Recursividad

Recursión lineal 

En la recursión lineal cada llamada recursiva genera, como mucho, otra llamada recursiva. Se pueden distinguir dos tipos de recursión lineal atendiendo a cómo se genera resultado.

int factorial(int n)
{
  if (n == 0) return 1;
  else return n*factorial(n-1);
}

Recursión No-Lineal

Alguna llamada recursiva puede generar más de una llamada a la función. Uno de los centros más típicos son los números de Fibonacci, números que reciben el nombre del matemático italiano que los descubrió. Estos números se calculan mediante la fórmula: 

#include <stdio.h>

long fibonacci (int); 

int main() { 

         int n= 30; 

         printf("El %dº número de Fibonacci es %ld\n", n, fibonacci(n)); 

} 

long fibonacci(int n) { 

 if (1 == n || 2 == n) { 

         return 1; 

 } 

else { 

       return (fibonacci(n-1) + fibonacci(n-2)); } 

} 

Recursión a la cola 

En la recursión lineal final el resultado que es devuelto es el resultado de ejecución de la última llamada recursiva. Un ejemplo de este cálculo es el máximo común divisor, que puede hallarse a partir de la fórmula:

#include <stdio.h>

long mcd(long,long);

int main(int argc, char *argv[]){

        long a= 4454,b= 143052;

        printf("El m.c.d. de %ld y %ld es %ld\n",a,b,mcd(a,b));

} 

long mcd(long a, long b){

        if (a==b){ 

                return a;

        }

        else {

                if (a<b){ 

                          return mcd(a,b-a);

                } 

                else{ 

                       return mcd(a-b,b);

                }

}

Recursión Mutua

Implica más de una función que se llaman mutuamente. Un ejemplo es el determinar si un número es par o impar mediante dos funciones:

#include <stdio.h>

long fibonacci (int); 

int main(){ 

        int n= 30; 

        if (par(n)) 

                 printf("El número es par"); 

        else 

                 printf("El número es impar"); 

} 

int par(int n){ 

        if (n==0) 

                 return 1; 

        else 

                 return (impar(n-1)); 

} 

int impar(int n){ 

         if (n==0) 

                 return 0; 

         else 

                 return(par(n-1)); 

}