Funciones recursivas


Hoy en el foro alguien ha preguntado que cómo podría hacer un programa que le mostrara una lista de todas las posibles combinaciones de un número binario de n cifras. Por ejemplo si n = 3, debe mostrar:


000
100
010
110
001
101
011
111

Le he comentado que es simple con funciones recursivas, pero después, viendo que estoy en globales y que voy justo de tiempo, he decidido tirar tiempo de estudio a cambio de programarla.

Una función recursiva es una función que se llama a si misma. Un ejemplo famoso es la serie de Fibonacci, claramente recursiva. En matemáticas, una serie recursiva es aquella en la que cada elemento depende de alguna manera del anterior o de un conjunto de los anteriores. Por ejemplo la de Fibonacci se define como fib(n) = fib(n-1) + fib(n-2) Con condiciones iniciales (siempre necesarias) fib(0) = 1 y fib(1) = 2. La serie para los primeros elementos es: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... . (Como curiosidad matemática, si desarrollamos la función fib(n) en función únicamente del elemento n, y no de los anteriores, nos encontramos con la famosa razón aurea, \frac{1+\sqrt{5}}{2}, uno de los números irracionales más famosos junto con \pi y con el número \rm e).

Bien, esta función de fibonacci, al ser recursiva, debe ser programable del mismo modo. Podemos crear la función recursiva que lo único que haga sea ver si ha llegado a las condiciones inciales, es decir, si n=0 o si n=1, y si no ha llegado simplemente se llama a si misma sumando los dos términos anteriores. Hagásmolo, y se verá lo sencillo que es.

La función en C podría ser:

int fibonacci(int n) {
    if (n==1) return 1;
    else if (n==2) return 2;
    else return fibonacci(n-1)+fibonacci(n-2);
}

Es simple. Esta función es poco eficiente puesto que depende de dos elementos anteriores y tiene que calcular cada elemento de la serie más de una vez. Sería mucho más eficiente programarla con un for de manera que recorra la serie linealmente, pero esto está bien para ver las funciones recursivas.

Vayamos ahora con la función del principio. No es nada complicada, lo que haremos será hacer una función que reciba n (número de caracteres) y un puntero a una cadena en la que iremos guardando cada posibilidad.

La función mete un 0 en la cadena, mira si ha llegado al final, en ese caso muestra la cadena, en caso vuelve a llamarse a si misma pasándole el mismo puntero pero n-1 como número, ya que ya le hemos metido un número. Después hacemos lo mismo pero metiendo un 1 en vez de un 0. Lo que hace la función es ir recorriendo cada posibilidad. Es muy útil para entenderlo hacerse un esquema con la cadena de caracteres y recorrer la función mentalmente. Mientras lo haces vas cambiando la cadena para ver lo que va pasando. Verás que no es nada complicado. La función quedaría así:

void recurs(int n,char *cad) {
	cad[n-1] = '0';
	if (n == 1) printf("%s\n", cad);
	else recurs(n-1,cad);
	cad[n-1] = '1';
	if (n == 1) printf("%s\n", cad);
	else recurs(n-1,cad);
}

El código completo es el siguiente, lo puedes bajar como archivo aquí (y si haces click en la publi gracias 😉 , se que el host tarda un poco en cargar, pero ten paciencia, tengo colgados archivos del resto de tutoriales).

#include <stdio.h>
#include <stdlib.h>

long long int potencia(int n,int p) {
	int i =0;
	long long int result=n;
	for (i=0;i<p-1;i++) {
		result *=n;
	}
	return result;
}

void recurs(int n,char *cad) {
	cad[n-1] = '0';
	if (n == 1) printf("%s\n", cad);
	else recurs(n-1,cad);
	cad[n-1] = '1';
	if (n == 1) printf("%s\n", cad);
	else recurs(n-1,cad);
}

int main(int argc, char** argv) {
	printf("Número de caracteres de la cadena: ");
	int cad;
	scanf("%i",&cad);
	char *cadena = (char *) malloc (cad*sizeof(char));
	recurs(cad,cadena);
	printf("Impresas %Ld cadenas\n", potencia(2,cad));
	return 0;
}

Le he puesto también una función que calcula potencias, sólo para que al final muestre el número de cadenas que salen. Es combinatoria simple, el número de cadenas es una variación con repetición de dos elementos tomados de n en n. La fórmula sería 2^n. Puedes hacerlo también con la función pow de la librería math.h, pero me apetecía programarla a mano.

Hasta aquí este tutorial. Muchas gracias. Para cualquier duda no dudes en preguntar. Comenta si te gusta.

Un saludo.

Anuncios
Esta entrada fue publicada en Manuales, Tutoriales y etiquetada , , , , , , , , . Guarda el enlace permanente.

6 respuestas a Funciones recursivas

  1. sistro dijo:

    muy bueno
    intentare poner en practica todo esto
    gracias

  2. Pingback: Funciones recursivas | White-Hat Hacking

  3. Pingback: Funciones recursivas | White-Hat Hacking

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s