Definindo funções recursivas

Ver Todos os Exercícios

Teoria

Introdução

Fala aí, aqui é o Guga do Responde Aí! Tudo bem com você?

Nesse tópico, nós iremos transformar os dois algoritmos que nós vimos no tópico anterior para o estudo de algoritmos recursivos em funções recursivas na linguagem C.

Parece coisa de outro mundo, né?

Mas calma, você vai ver que não é impossível. Então, vamos nessa!

Função recursiva de soma

A primeira função que transferiremos do teórico para a linguagem C é a função soma. Ela tem como objetivo realizar a soma de todos os elementos de um vetor de 5 posições.

A primeira coisa que nós devemos fazer é definir a função, para isso devemos chamá-la de soma e reconhecer que o seu tipo de retorno é int, já que o seu resultado será a soma de 5 números inteiros. Além disso, deve ter como parâmetros o índice atual do vetor e um ponteiro para ele.

Não se preocupe com a parte dos ponteiros, nós falaremos sobre eles futuramente. Enquanto isso, apenas considere que é uma forma de transferir todas as informações sobre o vetor (que foi criado no escopo principal) para o escopo local da função.

A imagem a seguir ilustra como a definição da função deve ser realizada:

Com a função soma definida, podemos criar o seu caso básico. Isso é, em que momento das chamadas recursivas o problema atinge sua forma trivial.

Muito simples! Como o vetor só possui 5 posições, quando a instância de posição 5 for passada como parâmetro para função, a mesma deve retornar um valor 0 (para não interferir na soma) e efetivamente realizá-la a partir de uma soma trivial.

Dá uma olhadinha na imagem abaixo, ela nos mostra como o caso básico é encaixado em uma função recursiva:

Certo, mas como as instâncias são criadas? E mais, como a soma é realizada na volta da recursão?

Vamos analisar o código abaixo:

Basicamente, a função irá chamar a si mesma avançando uma posição pelos parâmetros, enquanto a variável pos não for igual a 5. No entanto, quando pos atinge o valor 5 é que a mágica realmente acontece.

Pois, o valor 0 será retornado e somado com o elemento na posição 4 do vetor, o resultado dessa operação, por sua vez, será retornado e somado com o valor do elemento da posição 3 e assim consecutivamente até que o resultado da soma dos 5 elementos seja retornado ao programa principal, para somente assim ser processado.

Eu sei que a coisa é meio maluca, mas uma dica de parceiro é imaginarmos todas as instâncias sendo criadas até que uma solução trivial é encontrada e da mesma forma imaginar como todas essas instâncias são retornadas na ordem de criação, gerando assim operações mais simples.

Função recursiva para o cálculo do fatorial

Beleza! Estamos pegando o jeito.

Assim como antes, a primeira coisa que devemos fazer é definir a função que será responsável por realizar o cálculo do fatorial de um número.

Essa função se chamará fat e terá seu retorno do tipo int, pois o resultado de sua operação é o fatorial de um número inteiro. Além disso, essa função deve ter apenas um parâmetro que é o número que terá o seu fatorial calculado.

A imagem a seguir ilustra como a função descrita pode ser definida:

Vamos agora para o caso básico, esse que só é encontrado quando n for igual a 0. Pois, por se tratar do fatorial de 0, temos como premissa que esse valor é 1, sendo ele o retorno da condição.

Para ficar mais fácil, podemos observar a imagem a seguir:

Ufa! Agora as coisas estão ficando mais direitas.

Mas então, você se lembra das regras dos algoritmos recursivos? Uma delas dizia que a cada criação de instância o caso básico deve estar mais próximo.

Para que isso aconteça, a função invocará a si mesma com parâmetros iguais a n – 1. Pois, quando o caso básico for verdadeiro, o valor 1 será retornado e multiplicado por 1 na instância anterior, o resultado dessa multiplicação, por sua vez, será multiplicado por 2 ao retornar novamente nas instâncias e assim sucessivamente até que o resultado de todas as multiplicações anteriores a n sejam, finalmente, multiplicadas por n.

Dessa forma, teremos o fatorial do número inicial, que será retornado ao escopo principal para ser processado.

No fim de tudo, a função fat deve ter a seguinte cara:

Muito massa, né?

Agora que nós já sabemos como definir funções recursivas, está na hora de resolvermos alguns exercícios de fixação.

Eu como sempre te esperarei na página aqui do lado.

Função recursiva para o cálculo do fatorial

Exercícios Resolvidos

Exercício Resolvido #1

Desenvolva uma função recursiva capaz de realizar a impressão de um número natural na base binária.

Passo 1

A primeira coisa que devemos fazer é definir um caso básico para a nossa função (aquele que vai impedir ela de criar instâncias infinitamente), para isso temos que pensar na maneira com que vamos resolver esse problema.

Nesse exemplo, utilizaremos sucessivas divisões por 2 analisando o resto de cada divisão, isso faz com que o nosso caso básico seja n = 0 , ou seja, paramos de realizar divisões quando o número já estiver totalmente dividido.

Só para lembrar... Se pegarmos todos os restos das divisões de um número por 2 (que se resumem apenas em 0 ou 1) teremos esse mesmo número na base binária.

Passo 2

Agora que já temos um caso básico, só nos resta pensar no passo de recursão que utilizaremos, que basicamente consiste em colocar na prática a nossa lógica de sucessivas divisões e análise de resto.

Onde imprimimos o resto da divisão de n (número recebido como parâmetro) por 2 e utilizamos uma chamada recursiva dessa função passando como parâmetro a divisão inteira (considera apenas a parte inteira) de n por 2.

Resposta

Dessa forma, podemos converter qualquer número natural para sua forma binária, simplesmente imprimindo os restos de sucessivas divisões desse número por 2 com chamadas recursivas.

Exercício Resolvido #2

Seja o somatório abaixo. Faça uma função recursiva para realizar o cálculo.

∑ i = 1 n i 2

Passo 1

Sempre quando vamos criar uma função recursiva nós temos que ter uma visão geral dela, para isso devemos primeiro declarar o seu escopo.

Como o somatório gerará um resultado inteiro, o tipo de retorno dessa função chamada s o m a t o r i o deve ser int. Além disso, essa função deve esperar como parâmetros o valor inicial i (que pelo somatório do enunciado é dado como 1) e o limite superior n .

Passo 2

Tendo em vista o escopo dessa função podemos agora definir o caso básico.

A lógica desse caso básico consistem em parar o somatório uma unidade depois de n que é o limite superior (e deve ser calculado). Nesse caso, a forma de parar e retornar nas instâncias criadas é retornar o valor 0 (que é nulo em uma soma).

Passo 3

Por fim, basta criarmos a regra de criação de instâncias (que praticamente é dada no enunciado).

Basicamente o que nós fazemos é calcular o quadrado de i e chamar recursivamente passando como parâmetro i + 1 a própria função. Isso fará com que quando o caso básico seja verdadeiro, essas instâncias comecem a retornar os resultados dos até que por último o primeiro quadrado de i seja somado com a soma de todos os quadrados seguintes até n .

Resposta

Isso pode parecer muito complicado, mas recursão é isso. Você avança em instâncias até o caso básico ser verdadeiros depois elas começar a retornar resultados que em conjunto resolvem o problema geral. Nesse caso, o somatório.