Desmistificando os algoritmos recursivos \| TreinaWeb Promoção no ar Matricule-se agora e garanta **54% de desconto** Termina em Tempo restante da oferta: 09 Horas 53 Min 09 Seg Tempo restante da oferta: 09 53 09 [Assinar →](https://www.treinaweb.com.br/checkout/pagamento/plano/anual?cupom=TW-SCLIENTE26) [ ](https://www.treinaweb.com.br) Explorar [ Quanto custa? ](#assinatura) [ FAQ ](https://www.treinaweb.com.br#faq) [Matricule-se](#assinatura) [ Entrar ](https://www.treinaweb.com.br/login) [ Início ](https://www.treinaweb.com.br) [ Artigos ](https://www.treinaweb.com.br/blog) Desmistificando os algoritmos recursivos [ Algoritmos ](https://www.treinaweb.com.br/blog/categoria/algoritmos) # Desmistificando os algoritmos recursivos Os algoritmos recursivos são fundamentais na solução de muitos problemas envolvendo a computação. Logo, é necessário compreender como eles funcionam. [ Daniel Viana ](https://www.treinaweb.com.br/blog/autor/daniel-viana) 10 anos atrás ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2021/05/desmistificando.jpg) Os algoritmos recursivos são fundamentais na solução de muitos problemas envolvendo a computação, ainda assim, muitos programadores os veem como algo complexo e de difícil implementação. Como disse o *prof. Siang Wun Song*: > Para fazer um procedimento recursivo é preciso ter fé. Calma! Apesar da fala do prof. Siang, implementar um algoritmo recursivo não é um bicho de sete cabeças. Veremos alguns passos para compreendê-los de vez. o/ [ ![C Básico](https://d2knvm16wkt3ia.cloudfront.net/assets/svg-icon/c.svg) Curso C Básico Conhecer o curso ](https://www.treinaweb.com.br/curso/c-basico) Primeiro devemos entender o que é a recursividade. Uma função recursiva chama a si mesma dentro do próprio escopo. Pode ser uma recursão direta onde uma função *A* chama a própria função *A* ou uma recursão indireta onde uma função *A* chama uma função *B* que por sua vez chama a função *A*. Além de chamar a si mesma, a função recursiva deve possuir uma condição de parada que a impedirá de entrar em loop infinito. Antes de criar uma função recursiva para determinado problema, é preciso saber se ele possui uma estrutura recursiva. Neste caso, devemos verificar se parte do problema possui o mesmo tipo do original, assim podemos dizer que a solução para ele é a recursividade. Para compreender melhor, vamos analisar o caso do somatório onde temos um número natural `n >= 0` e queremos descobrir a *soma de todos os números de `n` até `0`*. Antes de criar o algoritmo devemos extrair dois elementos do problema: O **caso base** que se tornará a condição de parada e o **passo recursivo**. Vejamos algumas possíveis iterações do problema: ![](https://d2m498l008ebpa.cloudfront.net/2016/12/itera--o-somat-rio---1.png) No caso do somatório, é possível identificar que para cada valor de `n` o último elemento sempre é `0`, assim podemos confirmar que este é o caso base. Analisando um pouco mais as iterações temos que *para cada valor de `n` vamos diminuindo em `1` até que chegue ao valor `0`*. ![](https://d2m498l008ebpa.cloudfront.net/2016/12/itera--o-somat-rio---2.png) Assim, nós temos que o somatório de um número natural `n` é o próprio `n` adicionado ao somatório do número antecessor (Somatório de `n = n + (n-1) + (n-2) + ... + 0`). Logo, o nosso passo recursivo é `n + soma(n-1)`. Sabemos que o caso base é `0` e o somatório de `0` é ele mesmo, estão essa será a nossa condição de parada. O nosso passo recurso é `n + soma(n-1)`, assim já temos os elementos da nossa função recursiva e podemos criá-la: ```c int soma(int n){ if(n == 0) return 0; return n + soma(n-1); } ``` Esta é a implementação em *C* para resolver o problema de forma recursiva. Para um número natural `n` informado, a função irá executar até que seja encontrado o caso base e assim retornar o valor do somatório. Vamos analisar outro problema clássico que pode ser resolvido com recursividade: o fatorial de um número natural `n >= 1`. O fatorial é bem semelhante ao somatório, porém é feito com multiplicação sucessiva. Vamos analisar as possíveis iterações: ![](https://d2m498l008ebpa.cloudfront.net/2016/12/itera--o-fatorial---1.png) ![](https://d2m498l008ebpa.cloudfront.net/2016/12/itera--o-fatorial---2.png) No exemplo do fatorial, o nosso caso base é `1`, portanto, a nossa condição de parada será verificar se o número é `1` e, caso seja, a função deverá retorná-lo. Também é possível definir o nosso passo recursivo: `fatorial de n = n x (n - 1) x (n - 2) x ... x 1` logo `n! = n x fatorial(n - 1)`. Por fim, chegamos à seguinte implementação em *C*: ```c int fatorial(int n){ if(n == 1) return 1; return n * fatorial(n-1); } ``` Uma grande vantagem da recursividade é o fato de gerar uma redução no tamanho do algoritmo, permitindo descrevê-lo de forma mais clara e concisa. Porém, todo cuidado é pouco ao se fazer módulos recursivos. Basta seguir estes passos e você não terá grandes problemas. Como disse *L. Peter Deutsch*: > Iterar é humano, fazer recursão é divino. Um abraço e até a próxima! [ ![HTML5 + CSS3 - Propriedades e seletores avançados](https://d2knvm16wkt3ia.cloudfront.net/assets/svg-icon/html5-css3.svg) Curso HTML5 + CSS3 - Propriedades e seletores avançados Conhecer o curso ](https://www.treinaweb.com.br/curso/html5-css3-propriedades-e-seletores-avancados) - [ #C ](https://www.treinaweb.com.br/blog/tag/c) - [ #Estrutura de dados ](https://www.treinaweb.com.br/blog/tag/estrutura-de-dados) - [ #Ciência da computação ](https://www.treinaweb.com.br/blog/tag/ciencia-da-computacao) Autor ![Daniel Viana](//secure.gravatar.com/avatar/ee77d0cb4491d2d130f9f1093aabff4f?d=mm) ## Daniel Viana Instrutor, Desenvolvedor Android, Mestrando em Bioinformática pela UFMG, MBA Executivo em Gerenciamento de Projetos pela UCAM, Graduado em Ciência da Computação pela FUNIP, Membro da SBC, ACM e AB3C. [Todos os artigos](https://www.treinaweb.com.br/blog/autor/daniel-viana) ## Continue estudando Transforme leitura em prática com os cursos e formações da TreinaWeb. [Ver cursos](https://www.treinaweb.com.br/cursos) Continue lendo ## Artigos relacionados - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2021/02/c-sharp-consumindo-apis-com-flurl-400x280.png) [ C# ](https://www.treinaweb.com.br/blog/categoria/csharp) 6 anos atrás ## [ C# - Testando requisições com Flurl ](https://www.treinaweb.com.br/blog/c-testando-requisicoes-com-flurl) Implemente testes unitários em requisições HTTP com o auxílio de Flurl. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2021/02/c-sharp-consumindo-apis-com-flurl-400x280.png) [ C# ](https://www.treinaweb.com.br/blog/categoria/csharp) 6 anos atrás ## [ C# - Consumindo APIs com Flurl ](https://www.treinaweb.com.br/blog/c-consumindo-apis-com-flurl) Veja como consumir dados de uma API no C#, utilizando a biblioteca Flurl. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2020/11/C-SHARP-PROPRIEDADES-INIT-RECORD-400x280.png) [ C# ](https://www.treinaweb.com.br/blog/categoria/csharp) 6 anos atrás ## [ C# 9.0 - Inteiros nativos e inferência de tipos ](https://www.treinaweb.com.br/blog/c-9-0-inteiros-nativos-e-inferencia-de-tipos) Conheça os novos tipos de dados introduzidos no C# 9.0, os inteiros nativos e os novos recursos da inferência de tipos. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2020/11/C-SHARP-PROPRIEDADES-INIT-RECORD-400x280.png) [ C# ](https://www.treinaweb.com.br/blog/categoria/csharp) 6 anos atrás ## [ C# 9.0 - Programas top-level e Pattern Matching ](https://www.treinaweb.com.br/blog/c-9-0-programas-top-level-e-pattern-matching) Dando continuidade ao nosso estudo do C# 9.0, neste artigo veremos dois novos recursos dele: Programas top-leve e Pattern Matching. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2020/11/C-SHARP-PROPRIEDADES-INIT-RECORD-400x280.png) [ C# ](https://www.treinaweb.com.br/blog/categoria/csharp) 6 anos atrás ## [ C# 9.0 - Propriedades init e record ](https://www.treinaweb.com.br/blog/c-9-0-propriedades-init-e-record) Já estamos no C# 9.0, a nova versão lançada no .NET Conf 2020 trouxe uma série de novos recursos, veja neste artigo dois deles: propriedades init e record. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2023/11/Clean-Architecture-400x280.png) [ Arquitetura de Software ](https://www.treinaweb.com.br/blog/categoria/arquitetura-de-software) 3 anos atrás ## [ O que vem a ser a Clean Architecture? ](https://www.treinaweb.com.br/blog/o-que-vem-a-ser-a-clean-architecture) Confira nesse artigo uma introdução do que é a Clean Architecture, quais seus componentes e os benefícios ao utilizar essa arquitetura. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2023/12/CAPA-PYTHON-400x280.jpg) [ Desenvolvimento Back-end ](https://www.treinaweb.com.br/blog/categoria/desenvolvimento-back-end) 4 anos atrás ## [ Como trabalhar com data e hora no Python ](https://www.treinaweb.com.br/blog/como-trabalhar-com-data-e-hora-no-python) Como trabalhar com data e hora no Python com Datetime. No decorrer deste artigo, veremos exemplos de como utilizar o módulo datetime... Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2022/10/o-que-e-e-como-comecar-com-golang-400x280.jpg) [ Desenvolvimento Back-end ](https://www.treinaweb.com.br/blog/categoria/desenvolvimento-back-end) 4 anos atrás ## [ Como instalar a Golang e executar nosso primeiro exemplo ](https://www.treinaweb.com.br/blog/como-instalar-a-golang-e-executar-nosso-primeiro-exemplo) Neste artigo iremos aprender como instalar a Golang nos sistemas Windows, Linux e macOS e como executar nosso primeiro exemplo. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2022/08/DESENOLVEDOR-MOBILE-INVESTIR-CARREIRA-400x280.png) [ Desenvolvimento Mobile ](https://www.treinaweb.com.br/blog/categoria/desenvolvimento-mobile) 4 anos atrás ## [ Desenvolvedor mobile: por que investir nessa carreira? ](https://www.treinaweb.com.br/blog/desenvolvedor-mobile-por-que-investir-nessa-carreira) Carreira mobile tem muitas oportunidades, por isso vamos ver o que você precisa saber para entrar ou migrar para essa área tão promissora. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2022/05/como-instalar-o-csharp-e-nosso-primeiro-exemplo-400x280.png) [ C# ](https://www.treinaweb.com.br/blog/categoria/csharp) 5 anos atrás ## [ Conhecendo variáveis e constantes no C# ](https://www.treinaweb.com.br/blog/conhecendo-variaveis-e-constantes-no-csharp) Conheça neste artigo os tipos de dados presentes no C# e a sintaxe para que possamos declarar variáveis e constantes. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2022/05/como-instalar-o-csharp-e-nosso-primeiro-exemplo-400x280.png) [ C# ](https://www.treinaweb.com.br/blog/categoria/csharp) 5 anos atrás ## [ Como instalar o C# e nosso primeiro exemplo ](https://www.treinaweb.com.br/blog/como-instalar-o-csharp-e-nosso-primeiro-exemplo) Neste artigo veremos como instalar o C# nos sistemas Windows, Linux e MacOS e também veremos como escrever nosso primeiro programa. Ler artigo - ![](https://dkrn4sk0rn31v.cloudfront.net/uploads/2022/01/criando-uma-api-com-spring-data-jpa-e-spring-web-400x280.png) [ Desenvolvimento Back-end ](https://www.treinaweb.com.br/blog/categoria/desenvolvimento-back-end) 5 anos atrás ## [ Criando uma API com Spring Data JPA e Spring Web ](https://www.treinaweb.com.br/blog/criando-uma-api-com-spring-data-jpa-e-spring-web) Neste artigo vamos aprender como criar uma API com persistência de dados utilizando o Spring Web MVC e o Spring Data JPA. Ler artigo ## Um ano de acesso total para você viver de programação. Todos os cursos e formações da TreinaWeb numa única assinatura, com professores que atuam no mercado, suporte direto e certificados. Do primeiro `console.log` ao mercado de trabalho. - **1 ano** de acesso a **todos os cursos** - Cursos novos **toda semana** - Suporte **direto com professores** - Plano de carreira **personalizado** - **Certificados digitais** inclusos - **Aplicativos** para Android e iOS, com **acesso offline** **Garantia incondicional de satisfação** Teste por 7 dias e, se não fizer sentido para você, devolvemos seu dinheiro. ### Acesso completo a todos os cursos e dezenas de Formações. 12 meses Economize R$ 840,00 54% OFF de 12x R$ 129,00 por apenas 12x R$ 59,00 sem juros no cartão de crédito ou R$ 599,00 à vista Oferta termina em **09h 53min 09s** - Acesso imediato e ilimitado durante 1 ano. - Plano de carreira personalizado. - Suporte direto com professores. - E muito mais! [Matricule-se agora](https://www.treinaweb.com.br/checkout/pagamento/plano/anual?cupom=TW-SCLIENTE26) [ ](https://www.treinaweb.com.br) Escola online de programação, tecnologia e IA. - [ ](https://www.facebook.com/TreinaWeb/) - [ ](https://www.instagram.com/treinaweb/) - [ ](https://www.youtube.com/user/TreinaWeb) - [ ](https://twitter.com/treinaweb) - [ ](https://www.linkedin.com/company/treinaweb) - [ ](https://github.com/treinaweb) ## Inscreva-se em nossa newsletter Receba lançamentos, promoções e novidades. Seu nome Seu WhatsApp Seu melhor e-mail Inscrever-se ## Cursos - [ Base para Devs ](https://www.treinaweb.com.br/categoria/base-para-devs) - [ Front-end ](https://www.treinaweb.com.br/categoria/desenvolvimento-front-end) - [ Back-end ](https://www.treinaweb.com.br/categoria/desenvolvimento-back-end) - [ Mobile ](https://www.treinaweb.com.br/categoria/desenvolvimento-mobile) - [ Bancos de Dados ](https://www.treinaweb.com.br/categoria/bancos-de-dados) - [ Cloud ](https://www.treinaweb.com.br/categoria/cloud-computing) - [ IA ](https://www.treinaweb.com.br/categoria/ia) - [ E mais ](https://www.treinaweb.com.br/categoria/e-mais) - [ Ver todos os cursos ](https://www.treinaweb.com.br/cursos) ## Conteúdo - [ Formações ](https://www.treinaweb.com.br/formacoes) - [ Projetos práticos ](https://www.treinaweb.com.br/projetos-praticos) - [ Direto ao ponto ](https://www.treinaweb.com.br/direto-ao-ponto) - [ Planos ](https://www.treinaweb.com.br#assinatura) - [ Depoimentos ](https://www.treinaweb.com.br#depoimentos) - [ Comunidade ](https://www.treinaweb.com.br#comunidade) - [ Corpo docente ](https://www.treinaweb.com.br#docente) ## A empresa - [ Sobre a TreinaWeb ](https://www.treinaweb.com.br#sobre) - [ Perguntas frequentes ](https://www.treinaweb.com.br#faq) - [ Vantagens de estudar na TreinaWeb ](https://www.treinaweb.com.br/vantagens-de-estudar-na-treinaweb) - [ Cursos para empresas ](https://www.treinaweb.com.br/empresas) - [ Sugira um novo curso ](https://www.treinaweb.com.br/sugerir-curso) - [ Trabalhe conosco ](https://www.treinaweb.com.br/trabalhe-conosco) - [ Artigos ](https://www.treinaweb.com.br/blog) - [ Desenvolvedores e agentes ](https://www.treinaweb.com.br/developers) - [ Contato ](https://www.treinaweb.com.br/contato) - [ Política de privacidade ](https://www.treinaweb.com.br/politica-de-privacidade) - [ Termos de uso ](https://www.treinaweb.com.br/termos-de-uso) ## Baixe nosso aplicativo [ Disponível na **App Store** ](https://apps.apple.com/us/app/treinaweb/id1322729447) [ Disponível no **Google Play** ](https://play.google.com/store/apps/details?id=br.com.treinaweb.mobile) Av. Paulista, 1765, Conj 71 e 72 · Bela Vista · São Paulo · SP · 01311-200 © 2004 – 2026 TreinaWeb Tecnologia LTDA · CNPJ 06.156.637/0001-58