Recursão - Potência

Olá!

Você lembra das famosas potências? Daquelas do tipo 2³?
Hoje vamos criar duas formas de realizar esse cálculo.
Queremos criar uma função que receba um número inteiro a (base) e outro n (expoente) e retorne o resultado da multiplicação de a por ele mesmo n vezes (ou, de um modo mais fácil, a elevado à n).

Primeiro, vamos pensar numa versão iterativa, utilizando laços de repetição.
Criamos uma variável para guardar o nosso resultado. Assim, para realizar a multiplicação de a por ele mesmo n vezes, podemos realizar com um laço for: E pronto! temos nossa função potencia:

Como já temos nossa versão iterativa, vamos agora pensar na versão recursiva.
Qual seria o caso base da nossa recursão?
Uma linha de raciocínio seria pensar em um a = 2 e n = 3.
2³ = 2 * (2²)
Certo? Pensando assim, podemos continuar:
2³ = 2 * (2²) = 2 * (2 * (2¹)) = 2 * (2 * (2 * (2^0)))
Logo, o nosso caso base é quando o expoente é zero, ou n == 0, que sabemos que o resultado é 1^[1]. E nosso passo da recursão é dado por base * potencia(base, expoente - 1).
Colocando assim, temos:
Potencia(a, n) = a * Potencia(a, n - 1).

Pronto! Temos nossa função recursiva!
Obs.: Perceba que a função funciona adotando n >= 0. Não estamos preocupados em tratar exceções como n = -1, por enquanto =)

Eu acho a função recursiva bem mais elegante =P
Mas é isso ai! Apenas mais um exemplo de recursão!

Até a próxima!

^[1] Curiosidade: Pra quem não sabe o porque de um número elevado a zero resultar em 1, o processo é esse: x/x = x¹ : x¹ = x^{1 - 1} = 1. Explicando: Se você tem 2 objetos e quer dividir para 2 pessoas, sabemos que o resultado é 1. Qualquer número dividido por ele mesmo resulta em 1. Logo, por propriedades de potência, quando há divisão de potências de mesma base pode-se manter a base e subtrair os expoentes, resultando em 2^0. =)

Recursão

Olá!
Quando você começa a estudar a Ciência da Computação, você aprende (ou pelo menos deveria aprender) muita matemática. Uma técnica matemática aplicada à essa ciência é recursão.
De acordo com o verbete Recursion, da Wikipedia:

"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.[1] The approach can be applied to many types of problems, and is one of the central ideas of computer science."

ou, em Português:

"Recursão na ciência da computação é um método onde a solução de um problema depende de soluções de problemas menores em instâncias do mesmo problema. O método pode ser aplicado em vários tipos de problemas, e é uma das ideias centrais da ciência da computação."

Há também uma frase muito legal para entender a recursão, que diz:

"Para entender a recursão, é preciso primeiro entender a recursão"

Hã? Calma, pequeno padawan. =)
Imagine o seguinte problema: Você está no seu colegial, e o seu professor de matemática que você adora tanto que até deixou você de recuperação pra não sentir saudades, pede uma lista enorme, só com fatoriais. Você, um aluno calmo e consciente, respira fundo e pensa, dentre seus pensamentos matemáticos: "Qual será a relação matemática entre todos esses fatoriais?"
Então, você tem uma luz, daquelas que iluminam quarteirão em dia de apagão, e escreve:

fatorial(n) =
| 1 ,se n = 0
| n * fatorial(n - 1) ,se n > 0

Claro! Se o número que ele pedir for zero, então eu sei que o resultado é 1, por definição. Mas se for maior do que zero, o resultado nada mais é do que ele vezes o fatorial do número anterior à ele! E então você faz no seu rascunho algumas provas reais:

fatorial(1) = 1 * fatorial(0) = 1 * 1 = 1
fatorial(2) = 2 * fatorial(1) = 2 * 1 = 2
fatorial(3) = 3 * fatorial(2) = 3* ( 2*fatorial(1)) = 3* ( 2* ( 1* fatorial(0))) = 3*2*1*1 = 6

Você acaba de entender a recursão!

Passar esse conceito para um algoritmo em C, é fácil. Ficaria dessa forma:
Perceba a estrutura recursiva da função.
Temos o caso base, que encerra a recursão em algum momento, para não entrar em algo infinito:
E então, o passo da recursão, que reduz o problema a uma instância menor, chamando a mesma função
Na grande maioria dos casos (pra não dizer todos), uma solução recursiva pode ser escrita de forma iterativa. Veja o exemplo que eu dei quando falei sobre laços de repetição: A função fatorial, em sua versão iterativa.

Uma função recursiva é, sem dúvida, muito elegante. Hoje, muitas pessoas que estão na área da computação não conseguem utilizar recursão, outras não a entendem, e outras sequer sabem da sua existência. Então, é algo que merece um pouco de estudo e atenção.
E lembre-se: Para fazer um procedimento recursivo, é preciso ter fé! =)

Vou postar mais alguns problemas com resoluções recursivas e, para comparação e estudo, suas soluções iterativas.

Até lá!

Vetores

Um vetor (ou array) é uma estrutura de dados que é capaz de armazenar objetos do mesmo tipo em uma sequência, ocupando posições consecutivas na memória.
Falarei hoje sobre a busca em vetores.

Um vetor v de tamanho n posições é dado pela notação v[n] .

Esse vetor possui objetos armazenados em suas posições v[0 ... n-1] , ou seja, se o vetor v possui 5 posições, o último objeto estará armazenado em v[4] .

A declaração de um vetor de inteiros possuindo 5 posições é dada por: int v[5];

A busca

Vamos pensar que nos foi dado um vetor v de números inteiros ( int ) de tamanho n, e nos pedem para encontrar certo número x.

Então, temos o vetor representado da seguinte maneira:

indices	0				n-1
valores	14	26	12	18	12

Então, temos que encontrar um índice k tal que v[k] == x .

Você deve estar pensando: "E se x não estiver no vetor? Ou quem sabe n = 0? O que fazer?".
Calma, pequeno padawan. Se isso ocorrer, podemos simplesmente devolver -1 para quem estiver perguntando. =)

Pensando assim, temos que conseguir uma forma de entrar nesse vetor e achar o que estão nos pedindo. Como fazer?
É isso ai! Esse algoritmo efetua a busca, e retorna o índice que representa a posição do valor pedido no vetor dado. =)