Con esta entrada vamos a aprender a realizar un simple ejercicio de recursividad en C. Este ejercicio consiste en la suma de los elementos de un vector (ordenado o sin ordenar) de forma recursiva en lenguaje C.

Recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas. Para que se entienda mejor a continuación se exponen algunos ejemplos:

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

En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)

Fuente: Wikipedia

Si alguien quiere saber más sobre la recursividad, puede leer el artículo entero en la wikipedia.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include
#include
 
int main()
{
    int n = 3;
    int t[] = {1,2,3,4};
 
    printf("Resultado de la suma recursiva: %d", sumaVector(t,n));
    return 0;
}
 
int sumaVector(int t[], int n){
    int r = 0;
 
    if(n==0){
        r += t[0];
    }else{
        r = t[n] + sumaVector(t,n-1);
    }
    return r;
}

Este es el codigo para la realización del ejercicio.

Este ejercicio no es nada complicado. El caso base es cuando llegamos al último elemento del vector, es decir, como vamos a empezar por el final (posición n-1), el final de la ejecución será cuando lleguemos al principio del vector (n=0).

Mientras no lleguemos al principio del vector, sumamos el elemento anterior al que estamos sumando restando en uno la posición (n-1) en la llamada recursiva.