Definindo funções recursivas

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 , 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.

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ú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 por 2.

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 e indicamos ao programa que ela espera como parâmetro apenas um número inteiro .

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 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.

Com o caso básico definido, a ideia é criar instâncias da recursão sempre subtraindo em 1, para quando o caso básico for verdadeiro ( 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 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 (ordem crescente) verificando se o número é par. Caso o número seja par, o mesmo será impresso na tela.

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 que recebe como parâmetros dois números inteiros e como parâmetro.

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 é . No caso, se durante as instâncias da recursão obtermos igual a , basta retornamos como máximo divisor comum.

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 é maior que . Caso seja, utilizamos a regra , caso contrário, temos que utilizar a regra . Utilizando essa regra de criação de instância, chegaremos em um momento em que , ou seja, temos o valor do máximo divisor comum.

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 deve ser int. Além disso, essa função deve esperar como parâmetros o valor inicial (que pelo somatório do enunciado é dado como 1) e o limite superior .

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 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).

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 e chamar recursivamente passando como parâmetro 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 seja somado com a soma de todos os quadrados seguintes até .

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 deve ser int. Além disso, ela espera como parâmetro um número também inteiro.

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 e .

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 ( e ) e retornar a soma entre eles (já que ), obtendo assim o n-ésimo valor da sequência de Fibonacci.

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 é int. Além disso, ela espera como parâmetro o número que terá o seu fatorial calculado.

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 igual a 0 como caso básico para retornarmos o valor 1 e impedirmos a criação de mais instâncias na recursão.

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

Nesse caso, chamaremos a função recursivamente passando como parâmetro 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 que é igual ao fatorial de .

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

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

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 assumir um valor superior a 100.

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 na instância atual e iremos passar como parâmetro de uma chamada recursiva. Isso fará com que todos os números sejam impressos desde o valor de da primeira instância até 100.

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

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

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 para impedirmos a criação de novas instâncias recursivas (o motivo disso vai ficar mais óbvio no próximo passo).

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 e chamar recursivamente a função passando como parâmetro o próprio e . Isso fará com que seja um contador das somas de (por isso o caso básico retorna nas instâncias recursivas quando ) fazendo com que seja somado com ele mesmo vezes, resultando assim em .