Recursión

Recursión

Recursividad: la recursión es la propiedad de ciertos objetos de definirse en base a sí mismos. En computación, bajo el enfoque de lenguajes de programación, la recursión es una forma de control de flujo basada en funciones que se llaman a sí mismas. Bajo el enfoque de un programador, es una forma computacional de resolver problemas. Los programadores por lo general ven la solución de problemas desde el enfoque iterativo, el enfoque recursivo, o una mezcla de ambos. Los pasos básicos para resolver un problema mediante el enfoque de la recursividad son:

Definir el caso base: el caso base es el caso en el cual la solución al problema es conocida de antemano.

Definir la expresión recurrente: la expresión recurrente denota el paso recursivo a seguir.

Ejemplo clásico: factorial de un numero

El factorial se define con la siguiente función:

1 si n = 0 o n = 1

factorial (n) =

n x (n-1)! Si n > 1

función factorial (n : entero) : entero

inicio

si ((n = 0) v (n = 1)) entonces //definición del caso base, aquí conocemos la solución

retornar 1

sino

retornar (n * factorial(n-1) ) //Paso recursivo

finsi

finfuncion

Ejemplos Programados (Lenguaje C) 

/*
 * Calcula Factorial!(n)
 * */
int Fact(n){
    //caso base

     if((n==0)||(n==1)){
        return 1;
    }
    else{
       //paso recursivo

       return n*Fact(n-1);
    }
}

/*
 * Calcula la potencia de un numero base elevado a un exponente exp
 * */
int CustomPower(int base, int exp){
    if(exp==0){
        return 1;
    }
    else{
        return base*CustomPower(base,exp-1);
    }
}

/*
 * Realiza la busqueda de un elemento element en un arreglo de forma recursiva
 * */
int RecSearch(int *array, int size, int element){
    int out=0;
    if(size==0){
        return out;
    }
    if(array[size]==element){
        out=1;
        return out;
    }
    if(size>0){
        return RecSearch(array,size-1,element);
    }
}

/*
 * EquallSequences verifica si dos arreglos array y array2 de tamaño size
 * son iguales (retorna 1 si son iguales, 0 de lo contrario).
 * */
int EquallSequences(int *array, int *array2, int size){
    int eq=0;
    if(size==0){
        return eq;
    }
    if(array[size]!=array2[size]){
        eq=1;
        return eq;
    }
    else{
        return EquallSequences(array,array2,size-1);
    }
}

 /*
 * Cuenta cantidad de numeros positivos y cantidad de numeros negativos en un
 * arreglo array de tamaño size. El cambio queda reflejado en poscounter y negcounter,
 * variables pasadas por referencia.
 * */
void PositiveNegativeCounter(int *array, int size, int *poscounter, int *negcounter){
    if(size<0){
        *poscounter=*poscounter+0;
        *negcounter=*negcounter+0;
    }
    else{
        if(array[size]<0){
            *negcounter=*negcounter+1;
        }
        if(array[size]>0){
            *poscounter=*poscounter+1;
        }
        PositiveNegativeCounter(array,size-1,poscounter,negcounter);
    }
}