Recursão, pode ser definida em termos matemáticos ou de programação. Como este é um artigo de programação e as funções em C podem chamar a si mesmas, definiremos que uma função é recursiva se ela chama a si mesma em seu escopo. Recursão é o processo de definir algo em termo de si mesmo, e também é chamado de definição circular.

É necessário tomar um certo cuidado quando for construir funções recursivas, já que é muito fácil criar uma recursão sem fim, terminando o programa. Todo código recursivo deve conter uma condição para pausa e o programador deve garantir que toda vez que a função for chamada, essa condição será testada e, acima de tudo, deve reforçar um comportamento que faça o desenvolvimento da função caminhar em direção a essa condição.

Não adianta colocar uma condição como "se X == 0, termine", se a função incrementa X a cada chamada. Abaixo, alguns códigos ilustrando funções recursivas.

1. Fatorial:

O fatorial de um número é dado pela multiplicação de todos os valores menores que o número e maiores que 1 (um).

fat(n) = fat(n) * fat(n - 1) * fat(n - 2) * ... * fat(1)

Fácil perceber que ela se define em termos de si mesma.

/* fat.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

double fat (double n)
{
	if (n == 1) return 1;

	return n * fat(n - 1);

	// return (n == 1) ? 1 : n * fat(n - 1);
}

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

	for (i = 1; i < argc; i++)
		printf("%s: %.0lf
", argv[i], fat( atof(argv[i])));

	return 0;
}

2. Fibonacci:

Leonardo Bonacci (1170-1250), também conhecido como Fibonacci, foi um matemático italiano considerado o mais brilhante matemático da Era Medieval. Atribui-se a ele a "criação" da sequência Fibonacci, onde um dado número é definido pela soma dos dois números anteriores. As exceções são os números 0 (zero) e 1 (um), cujo valor na sequência é 1 (um).

Fonte: Fibonacci « wikipedia.org

É fácil perceber que a definição desta sequência é recursiva, uma vez que ela é definida em termo de si mesma.

fib(n) = fib(n - 1) + fib(n - 2)

/* fib.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

double fib (double n)
{
	if (n == 0 || n == 1) return 1;

	return fib(n - 1) + fib(n - 2);
	// return (n == 0 || n == 1) ? 1 : fib(n - 1) + fib(n - 2);
}

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

	for (i = 1; i < argc; i++)
		printf("%s: %.0lf
", argv[i], fib(atof(argv[i])));

	return 0;
}

Através da imagem, podemos perceber como a complexidade aumenta absurdamente, à medida que 'n' aumenta. Também podemos perceber a quantidade imensa de chamadas às funções.

* Lembre-se: cada chamada à função, requer um quadro na pilha (registro de ativação, ou Stack Frame) e isso consome memória! Quando for desenvolver rotinas recursivas, pense em como ela vai se comportar na memória, isso é muito importante!

3. Busca Binária em Matrizes:

Matrizes normalmente são usadas para armazenar sequências congruentes de dados, e a melhor forma de armazenar esses dados é guardando-os de forma ordenada. O problema com matrizes, é que o tempo de inserção, remoção e busca é muito ruim - O(n). O algoritmo de busca binária consiste em dividir o número de elementos da matriz pela metade e analisar esse elemento mediano. Se o elemento procurado for menor que o elemento mediano, então, descartamos a metade superior da matriz, e realizamos a operação novamente na metade inferior.

O tempo gasto para esse algoritmo achar um dado elemento, é de "O(lg(n))" no pior caso, e "O(1)" no melhor caso. Uma melhora considerável na performance! Também é fácil perceber que a função de busca binária é um algoritmo que se define em termos de si mesmo, portanto, recursivo.

/* bbin.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int bbin (int *a, int min, int max, int info)
{
	int pos = (min + max) / 2;

	if (a[pos] == info) return pos;
	else if (min >= max) return -1;
	else if (info > a[pos]) return bbin(a, pos + 1, max, info);
	else return bbin(a, min, pos - 1, info);

	return -1;
}

int main (void)
{
	int a[10] = {1,2,3,4,5,6,7,8,9,10};

	printf("1: %d
", bbin(a, 0, 10, 1));
	printf("5: %d
", bbin(a, 0, 10, 5));
	printf("8: %d
", bbin(a, 0, 10, 8));
	printf("0: %d
", bbin(a, 0, 10, 0));
	printf("9: %d
", bbin(a, 0, 10, 9));

	return 0;
}

Muito interessante, mas será que realmente é eficiente? Vamos construir outro programa com a função de busca binária e gerar uma matriz de 50.000 elementos inteiros, organizados sequencialmente e então, pediremos ao usuário para digitar qualquer valor e contaremos quantos passos a função vai gastar para encontrar tal elemento.

Teoricamente, nunca poderão ocorrer mais de 16 operações, já que: 2^16 = 65.536

/* bbin2.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber : enzoferber@gmail.com
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define LIMIT		50000

int counter;

int bbin (int *a, int min, int max, int info)
{
	int pos = (min + max) / 2;

	counter++;

	if (a[pos] == info) return pos;
	else if (min >= max) return -1;
	else if (info > a[pos]) return bbin(a, pos + 1, max, info);
	else return bbin(a, min, pos - 1, info);

	return -1;
}

int main (void)
{
	int a[ LIMIT ];
	register int i;
	int n;

	for (i = 0; i < LIMIT; i++)
		a[i] = i + 1;

	printf("Digite -1 para sair

");
	while (1) {
		printf("Digite um número: ");
		scanf("%d", &n);

		if (n == -1) break;

		// contador
		counter = 0;

		printf("Posicao no vetor: %d
", bbin(a, 0, LIMIT, n));
		printf("Operacoes necessarias: %d

", counter);
	}

	return 0;
}

Excelente, funcionou! E o número de operações não passou de 16! Teste você mesmo com os números 150, 25000, 25001, 12499, 12500 e 6250. Em uma pesquisa linear, usaríamos 12500 comparação para achar o número 12500. Com esse algoritmo achamos em apenas 2!

Uma árvore com 1,6 x 10^60 elementos não precisa de mais que 200 operações de comparação para achar o elemento procurado, inseri-lo ou removê-lo! Genial! Agora já sabe como os bancos de dados como o MySQL funcionam (na verdade, a estrutura usada não é uma árvore binária simples como a que vamos implementar nesse artigo, é uma versão muito melhor e mais avançada).

O grande problema é que não podemos usar matrizes para armazenar grandes quantidades de informações em grandes aplicações ou em computadores onde a memória disponível não seja tão disponível assim (hoje em dia não temos muito problema com memória para pequenas e médias aplicações, mas é sempre bom pensar em termos de escalabilidade e estabilidade, quando for desenvolver qualquer tipo de programa).

Já imaginou implementar busca binárias em listas duplamente encadeadas? Essa é a idéia por trás das árvores binárias!