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 de soma

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

Faça uma função recursiva que receba um número inteiro positivo para n e imprima todos os números pares de 0 até n em ordem crescente.

Passo 1

Vamos lá, a primeira coisa que nós temos que fazer para definirmos essa função é o seu escopo.

Como nós só temos que realizar a impressão dos números pares podemos utilizar o tipo void, ou seja, se trata de uma função que não terá retorno de valor. Além disso, denominamos essa função como i m p r i m e P a r e indicamos ao programa que ela espera como parâmetro apenas um número inteiro n .

Passo 2

Agora que já temos o escopo da função definido, podemos declarar o caso básico dela.

Esse caso básico é bastante simples, como só recebemos um número n como parâmetro, iremos utilizar ele para indicar ao programa quando as instâncias da recursão devem ser retornadas.

Nós vamos entender isso melhor no próximo passo, vem comigo.

Passo 3

Com o caso básico definido, a ideia é criar instâncias da recursão sempre subtraindo n em 1, para quando o caso básico for verdadeiro ( n igual a 0) retornarmos nas instâncias verificando se o número é par.

A grande sacada dessa função é primeiro avançarmos nas instâncias para atingirmos n com o valor 0 (condição básica), quando isso acontece o caso básico fará com que as instâncias de recursão retornem de 0 a n (ordem crescente) verificando se o número é par. Caso o número seja par, o mesmo será impresso na tela.

Resposta

Ei, a resposta está no passo a passo :)

Exercício Resolvido #3

O máximo divisor comum (MDC) de dois números inteiros x e y pode ser calculado usando-se uma definição recursiva:

M D C x ,   y = M D C x - y ,   y   s e   x > y

Além disso, sabe-se que:

M D C x ,   y = M D C ( y ,   x )

M D C x ,   x = x

Passo 1

Vamos lá, a primeira coisa que nós temos que fazer para criarmos essa função é definir o escopo da nossa função.

Com isso, sabemos que se trata de uma função com retorno de valor inteiro (o M.D.C) chamada m d c que recebe como parâmetros dois números inteiros x e y como parâmetro.

Passo 2

Agora que já temos uma visão geral da nossa função, podemos definir o caso básico que limitará as chamadas recursivas.

Um aspecto super interessante desse exercício é que podemos utilizar como caso básico uma das propriedades dadas no enunciado, que é M D C x ,   x = x . No caso, se durante as instâncias da recursão obtermos x igual a y , basta retornamos x como máximo divisor comum.

Passo 3

Com o nosso caso básico prontinho, podemos definir a regra que irá criar as instâncias recursivas.

Basicamente nós simplesmente temos que fazer a verificação de x é maior que y . Caso seja, utilizamos a regra M D C x ,   y = M D C ( x - y ,   y ) , caso contrário, temos que utilizar a regra M D C x ,   y = M D C ( y - x ,   x ) . Utilizando essa regra de criação de instância, chegaremos em um momento em que x = y , ou seja, temos o valor do máximo divisor comum.

Resposta

Ei, a resposta está no passo a passo :)

Exercício Resolvido #4

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.

Exercício Resolvido #5

Elabore uma função recursiva que dado um número n retorne o n-ésimo termo da sequência de Fibonacci. Considere a seguinte sequência:

0 ,   1 ,   1 ,   2 ,   3 ,   5 ,   8 ,   13 …

Passo 1

Para iniciarmos o desenvolvimento da nossa função, temos que primeiro definirmos o seu escopo.

Para isso, como se trata de uma função que retorna o n-ésimo termo da sequência de Fibonacci, o tipo de retorna da função chamada f i b o n a c c i deve ser int. Além disso, ela espera como parâmetro um número n também inteiro.

Passo 2

Agora que já temos uma visão geral da nossa função, podemos definir o caso básico dela.

Esse caso básico não se trata de um limitador de criação de instâncias recursivas, mas sim de uma solução para o caso em que a entrada é o primeiro ou segundo termo da sequência. Isso acontece, pois esses termos não são calculados e servem como base para o cálculo da sequência já que o n-ésimo termo é a soma entre os termos n - 1 e n - 2 .

Passo 3

Por fim, agora que já temos um contorno para os dois primeiros termos, podemos criar uma regra de chamadas recursivas para o cálculo de qualquer termo da sequência.

Essa regra nada mais é do que se chamar recursivamente para calcular o valor da sequência dos dois termos anteriores a n ( n - 1 e n - 2 ) e retornar a soma entre eles (já que n = ( n - 1 ) + ( n - 2 ) ), obtendo assim o n-ésimo valor da sequência de Fibonacci.

Resposta

Ei, a resposta está no passo a passo :)

Exercício Resolvido #6

Faça uma função recursiva capaz de calcular o fatorial de um número n recebido como parâmetro.

Passo 1

Vamos começar o desenvolvimento dessa função pelo seu escopo.

Como se trata do fatorial de um número, o tipo de retorno dessa função chamada f a t o r i a l é int. Além disso, ela espera como parâmetro o número n que terá o seu fatorial calculado.

Passo 2

Agora que nós sabemos quais são as entradas e saídas esperadas de nossa função, podemos definir o caso básico dela.

Quando nos referimos ao cálculo do fatorial de um número, sabemos que o fatorial de 0 sempre será 1, logo, utilizaremos n igual a 0 como caso básico para retornarmos o valor 1 e impedirmos a criação de mais instâncias na recursão.

Passo 3

Por fim, basta definirmos a regra de criação das instâncias recursivas de nossa função.

Nesse caso, chamaremos a função f a t o r i a l recursivamente passando como parâmetro n - 1 até que o caso básico seja verdadeiro e o valor 1 seja retornando. Nesse momento, a recursão irá retornar solucionando as multiplicações até a primeira instância criada, que por sua vez retornará a multiplicação de n * n - 1 ! que é igual ao fatorial de n .

Resposta

Ei, a resposta está no passo a passo :)

Exercício Resolvido #7

Elabore uma função recursiva que imprimira todos os números até 100 a partir de um número i inteiro recebido como parâmetro.

Passo 1

Iniciando pelo escopo da função, podemos definir o seu escopo da seguinte forma:

Onde nos referimos a uma função chamada c o n t a g e m sem retorno que espera como parâmetro um número inteiro i que iniciará a contagem até 100.

Passo 2

Agora que já temos uma visão geral da nossa função, podemos definir o caso básico dela.

Que basicamente consiste em impedir a criação de novas instâncias quando i assumir um valor superior a 100.

Passo 3

Agora que já temos um caso básico, podemos criar uma regra para a criação das instâncias recursivas.

Onde simplesmente iremos imprimir o valor de i na instância atual e iremos passar i + 1 como parâmetro de uma chamada recursiva. Isso fará com que todos os números sejam impressos desde o valor de i da primeira instância até 100.

Resposta

Ei, a resposta está no passo a passo :)

Exercício Resolvido #8

Elabore uma função recursiva capaz de realizar o cálculo de uma multiplicação recebendo como parâmetro dois números inteiros n 1 e n 2 positivos.

Passo 1

Transferindo todas as informações do enunciado para o escopo de uma função chamada m u l t i temos o seguinte trecho de código:

Uma função com tipo de retorno int que espera como parâmetro dois números n 1 e n 2 também inteiros.

Passo 2

Agora que já sabemos as entradas e saídas esperadas da nossa função, podemos definir o caso básico que ela terá.

Nesse caso, utilizaremos a condição n 2 = 0 para impedirmos a criação de novas instâncias recursivas (o motivo disso vai ficar mais óbvio no próximo passo).

Passo 3

A grande sacada para calcular uma multiplicação através de uma função recursiva está na realização de múltiplas somas.

Por esse motivo podemos somar o valor de n 1 e chamar recursivamente a função m u l t i passando como parâmetro o próprio n 1 e n 2 - 1 . Isso fará com que n 2 seja um contador das somas de n 1 (por isso o caso básico retorna nas instâncias recursivas quando n 2 = 0 ) fazendo com que n 1 seja somado com ele mesmo n 2 vezes, resultando assim em n 1 * n 2 .

Resposta

Ei, a resposta está no passo a passo :)