Curso de C #25 - Funções recursivas (recursividade)

[Música] fala moçada beleza professor Bruno voltando com o nosso curso de c+ mais e na aula de hoje nós vamos aprender sobre recursividade que nada mais é quando eu tenho uma função que chama a si mesmo n vezes então eu tenho um controle eu preciso de um controle para poder encerrar essa chamada porque senão essa chamada vai ser infinita tá a gente tem que ter esse controle aí tem que ter esse cuidado obviamente dentro da função mas nada mais é do que isso eh sempre que eu tiver uma função que chama a si mesma Isso

se chama recursividade então na aula de hoje a aula é um pouco extensa nós vamos ver nós vamos entender o recurso e nós vamos ver algumas aplicações para esse recurso Ok então vamos pra prática vamos lá pro computador entender como que a gente faz esse processo aí de uma função chamar a si mesma logo depois da vinheta roda aí [Música] Então pessoal vamos lá aqui no computador então vamos entender aí e a recursividade como é que funciona como é que a gente implementa de forma básica uma recursividade eh entender de forma geral o conceito aí

de de de de eu criar uma função que vai chamar a si mesma então já tô com o código básico aqui da aula 25 e vou criar aqui uma função eh do tipo void onde eu vou eh onde essa função vai fazer uma contagem Ok vai escrever os números na tela até uma um determinado valor que eu indicar então por exemplo se eu indicar o valor 10 essa essa essa função vai escrever de 0 a 10 se eu indicar o valor 20 ela vai escrever de 0 a 20 e assim por diante certo então uma

função contador aí então o nome vai ser vou criar aqui com o nome conte mesmo tá de conte de de contador vou atribuir aqui dois parâmetros para essa são dois argumentos que eu vou chamar o primeiro aqui de num os dois int Ok e o segundo eh de con e contte também não dá né vou fazer o seguinte vou deixar contte com o nome do argumento e a função vou chamar de contador ok Fica mais fácil assim eu acho melhor eh o conte pro nome do argumento aqui e a função chamar contador Então o que

essa função vai fazer é simplesmente escrever na tela aí do do valor que eu indiquei do zero até o valor que eu indiquei suponhamos vamos começar aqui vamos fazer essa função sem recursividade como é que ficaria aqui por exemplo eu vou indicar só um parâmetro Ok só parâmetro num iria criar aqui uma vou criar até dentro do for não vou declarar aqui não vou usar o for criando uma variável essa variável em zero e indicar Enquanto essa variável for menor que num eu incremento o valor dessa variável na sequência eu dou um comando C aqui

para escrever o valor eh desse desse do valor do I Ok então o i Eli mais um barra n Então tá aqui uma função tá para poder eh escrever na tela aí de zero até o número que eu indicar deixa eu prototipar a função aqui e vamos chamar a função aqui ó contador e vou colocar aqui 10 onde eu quero que essa função escreva de zero até 10 Então por enquanto sem recursividade tá é uma função simples Opa deixa eu ver aonde que eu errei aqui deixa eu ver in at tá aqui ó é porque

eu não não inizi aqui com o zero Tá certo então é porque ficou errado ali pulei na digitação ali vamos lá compilando e executando Vamos ver que vai escrever de zero Ah no caso aqui nove né para incluir o 10 tem que colocar igual Beleza vai escrever de 0 a 10 se eu colocar aqui 20 ele vai escrever de 0 a 20 nada de novo até agora OK isso aqui a gente já sabe fazer é uma função muito simples só que eu quero implementar essa função usando a recursividade Então vamos lá eh deixa eu vou

deixar dessa forma aqui por enquanto só que eu vou adicionar aqui vou mudar a minha função vou adicionar um parâmetro a mais que vai ser um parâmetro contador Ok no caso eu não vou usar eh for não vou usar loop nenhum aí já é uma uma das vantagens da da dessa recursividade eu não vou precisar usar o loop porque eu como eu tenho uma função que vai chamar a si própria né eu não preciso implementar o for para poder criar uma rotina de de de execução executar mais de uma vez um determinado comando Então o

que eu vou escrever vou continuar aqui o que que eu vou fazer escrever na tela o valor de conte Tá certo que vai ser o contador inicial vai ter o valor de Contagem Inicial tá bom eh vai ser passado aqui nesse parâmetro inclusive nós temos que mudar aqui né o o o protótipo no caso tenho que incluir aqui eh o conte já vou inicializar ele zero tá como eu quero atribuir ele como para um argumento um valor padrão eu quero toda vez iniciar a contagem do zero então eu vou não vou me preocupar em passar

esse esse valor como argumento já que sempre vai ser zero então vou passar ele aqui eh como padrão no protótipo da protótipo da função então quando eu chamar a função eu não preciso mais indicar o valor de conte ele já tá ali como padrão Ok então vamos lá tá Por enquanto nada de novo também ainda nada de novo né então eu tenho aqui o o o c que faz a imprensão do valor de conte e agora vamos indicar aqui eh a condição de parada e chamada eh da função novamente então eu quero fazer uma verificação

que enquanto o valor de num nota que o valor de num é esse valor informado aqui tá ele não tá como padrão então tenho que informar esse valor que vai vir aqui pro n então enquanto de veja bem for maior do que o valor de conte qual que é o valor de conte zer vendo valor de conte é zer então quanto o valor de for maior que o valor de conte o que que eu vou fazer eu vou chamar aqui ó a função contador Ok eh passando os mesmos parâmetros eu preciso passar o n tá

então vou passar aqui O N E conte só que aí que vem o detalhe se eu passar assim Isso aqui vai entrar num Loop Infinito eu preciso incrementar o valor de conte tá Então veja bem salvei ali né conte vai iniciar em zero e o n vai iniciar em 20 então n é maior que conte não que ele faz ele chama a função contador passando novamente o parâmetro aqui no um que eu não mudei então passo 20 e conte que eu vou aumentar porque ele vai imprimir aqui certo Então veja bem eu vou incrementar o

valor de Conte mas não é que não aqui eu Não não vou fazer um pós incremento eu vou fazer um pré incremento Tá certo para ele incrementar eh fazer o incremento antes aí Então veja bem tô incrementando o valor de conte e agora vamos só rodar a função aqui que já vai funcionar Tá eu já tenho a recursividade aqui funcionando Olha que bacana tá vendo eh a primeira vez que entrou aqui ó o conte né o conte inicia em zero e o n é o valor que eu passei então ele faz a imprensão ele imprimiu

o quê conte zero Ok num é maior que conte não então o que que ele faz chama a função novamente passa o 20 e o conte incrementado Então veja bem É aqui ele vai passar o conte valendo 1 né 0 + 1 vale um então ele dá o c valendo um ok verifica num é maior que conte não então ele chama a função novamente passando o quê 20 e o conte incrementado valendo dois e assim por diante até que conte não seja até que num não seja mais maior que conte E aí ele finaliza e

a chamada né a função para de chamar a si própria e finaliza né ele sai aqui do do do contador né das chamadas do contador e prossegue o programa normalmente Então isso é recursividade então só para vocês entenderem como é que isso funciona e na memória eu vou colocar uma ilustração aqui do lado eh para vocês entenderem melhor gente cada chamada da função Isso aqui é uma coisa que a gente tem que colocar na cabeça pra gente entender bem recursividade cada chamada da função ela vai usar o seu próprio registro de ativação Tá certo que

por sua vez contém suas próprias variáveis e parâmetros tá pra gente entender Olha aí na ilustração é isso daqui ó tem a função M OK tá lá o registro de ativação na memória depois eu chamo a função contador tá função contador ali com valor zero né primeiro entrou ali o Conte com valor zero num meu caso aqui né o n com valor 20 o CTE com o valor zero depois a função eh faz o seu procedimento e chama novamente cria uma nova chamada para essa função ou seja vai ser um novo registro de ativação dessa

função tá ela vai ter e outra área para armazenar suas variáveis certo e aí ela chama novamente ou seja ela recebe um novo registro de ativação certo com uma nova posição na memória sua as suas variáveis seus parâmetros vão ter novas posições e assim por diante tá no nosso caso aqui eu tô fazendo aqui o exemplo com 10 né que tá com 20 vou mudar aqui para 10 também tá se eu tiver 50 chamadas eu vou ter eh 50 funções aí 50 novas funções cada uma em uma com com a sua determinada posição de memória

para suas variáveis e seus parâmetros Tá certo então gente isso é eh recursividade quando eu tenho uma função que chama a si própria Tá bom então pessoal eh essa aula ela ficou um pouco extensa na próxima aula eu eu eu vou vou voltar com esse assunto de recursividade Inclusive eu vou até deixar o afio aqui para vocês pra próxima aula eu quero que são exercícios padrões aí geralmente de faculdade Tá certo eu quero que vocês criam aí funções recursivas para fazer fatorial e e sequência Fibonacci fatorial eu creio que todo mundo sabe como é que

faz se não souber consulta o Google e fibonaci também se não souber consulta o Google aí o que que é uma sequência Fibonacci e tenta fazer esses dois programinhas aí um para para poder fazer o cálculo de fatorial e outro para poder fazer a sequência Fibonacci basicamente é isso aqui ó deixa eu dar uma explicação por exemplo e o que que seria 4 fatorial tá 4 fatorial é igual 4 x 3 x 2 x 1 o que que seria e 8 fatorial que que é o 8 fatorial é 8 x 7 x 6 x 5

x 4 x 3 x 2 x 1 tá bom isso aqui é o fatorial e o a Fibonacci Fibonacci a sequência é o seguinte deixa eu dar um exemplo aqui de Fibonacci por exemplo eu começo aqui com 0 1 uma forma fácil de entender é seria que o próximo número é esse é o 1 mais ó 1 mais o 0 que dá 1 o próximo é 1 mais 1 que dá 2 o próximo 2 + 1 que dá 3 o próximo 3 + 2 que dá 5 tá vendo o próximo 5 + 3 que dá

8 próximo 8 + 5 que dá 13 e assim por diante Isso é uma sequência Fibonacci Tá bom então eu quero que vocês e criam esses dois programinhas aí o para fazer o fatorial e para fazer a sequência Fibonacci Esse é o desafio para a próxima aula Ok em recursividade né pode até fazer sem recursividade só para vocês entenderem depois implementa aí a recursividade Tá bom então é isso daí pessoal quem não se inscreveu se inscreva no canal não se esqueça de clicar no joinha tá bom dúvidas e sugestões postem nos comentrios ou mandem por

e-mail vou ficando por aqui até a próxima aula tchau tchau