TechCodeview

A recursão é um conceito fundamental em ciência da computação e matemática que permite que funções se chamem a si mesmas, possibilitando a solução de problemas complexos por meio de etapas iterativas. Uma representação visual comumente usada para compreender e analisar a execução de funções recursivas é uma árvore de recursão. Neste artigo, exploraremos a teoria por trás das árvores recursivas, sua estrutura e seu significado na compreensão de algoritmos recursivos.

O que é uma árvore de recursão?

Uma árvore recursiva é uma representação gráfica que ilustra o fluxo de execução de uma função recursiva. Ele fornece uma análise visual das chamadas recursivas, mostrando a progressão do algoritmo à medida que ele se ramifica e, eventualmente, atinge um caso base. A estrutura em árvore ajuda a analisar a complexidade do tempo e a compreender o processo recursivo envolvido.

Estrutura da árvore

Cada nó em uma árvore de recursão representa uma chamada recursiva específica. A chamada inicial é representada na parte superior, com as chamadas subsequentes ramificando-se abaixo dela. A árvore cresce para baixo, formando uma estrutura hierárquica. O fator de ramificação de cada nó depende do número de chamadas recursivas feitas na função. Além disso, a profundidade da árvore corresponde ao número de chamadas recursivas antes de atingir o caso base.

Caso base

O caso base serve como condição de terminação para uma função recursiva. Define o ponto em que a recursão para e a função começa a retornar valores. Em uma árvore de recursão, os nós que representam o caso base são geralmente representados como nós folha, pois não resultam em chamadas recursivas adicionais.

Chamadas recursivas

Os nós filhos em uma árvore de recursão representam as chamadas recursivas feitas na função. Cada nó filho corresponde a uma chamada recursiva separada, resultando na criação de novos subproblemas. Os valores ou parâmetros passados ​​para essas chamadas recursivas podem diferir, levando a variações nas características dos subproblemas.

Fluxo de execução:

Atravessar uma árvore recursiva fornece insights sobre o fluxo de execução de uma função recursiva. A partir da chamada inicial no nó raiz, seguimos as ramificações para alcançar as chamadas subsequentes até encontrarmos o caso base. À medida que os casos base são atingidos, as chamadas recursivas começam a retornar, e seus respectivos nós na árvore são marcados com os valores retornados. O percurso continua até que toda a árvore tenha sido percorrida.

Análise de Complexidade de Tempo

As árvores recursivas auxiliam na análise da complexidade temporal dos algoritmos recursivos. Examinando a estrutura da árvore, podemos determinar o número de chamadas recursivas realizadas e o trabalho realizado em cada nível. Esta análise ajuda a compreender a eficiência geral do algoritmo e a identificar quaisquer potenciais ineficiências ou oportunidades de otimização.

Introdução

• Pense em um programa que determine o fatorial de um número. Esta função recebe um número N como entrada e retorna o fatorial de N como resultado. O pseudocódigo desta função será semelhante a,

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• A recursão é exemplificada pela função mencionada anteriormente. Estamos invocando uma função para determinar o fatorial de um número. Então, dado um valor menor do mesmo número, esta função chama a si mesma. Isto continua até chegarmos ao caso básico, no qual não há mais chamadas de função.
• A recursão é uma técnica para lidar com problemas complicados quando o resultado depende dos resultados de instâncias menores do mesmo problema.
• Se pensarmos em funções, dizemos que uma função é recursiva se continuar chamando a si mesma até atingir o caso base.
• Qualquer função recursiva possui dois componentes principais: o caso base e a etapa recursiva. Paramos de ir para a fase recursiva quando chegamos ao caso básico. Para evitar recursões infinitas, os casos base devem ser definidos adequadamente e são cruciais. A definição de recursão infinita é uma recursão que nunca atinge o caso base. Se um programa nunca atingir o caso base, o estouro de pilha continuará ocorrendo.

Tipos de recursão

De modo geral, existem duas formas diferentes de recursão:

• Recursão Linear
• Recursão em árvore
• Recursão Linear

Recursão Linear

• Uma função que chama a si mesma apenas uma vez cada vez que é executada é considerada linearmente recursiva. Uma boa ilustração da recursão linear é a função fatorial. O nome 'recursão linear' refere-se ao fato de que uma função linearmente recursiva leva um tempo linear para ser executada.
• Dê uma olhada no pseudocódigo abaixo:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Se observarmos a função doSomething(n), ela aceita um parâmetro chamado n e faz alguns cálculos antes de chamar o mesmo procedimento mais uma vez, mas com valores mais baixos.
• Quando o método doSomething() é chamado com o valor do argumento n, digamos que T(n) representa a quantidade total de tempo necessária para completar o cálculo. Para isso, também podemos formular uma relação de recorrência, T(n) = T(n-1) + K. K serve como constante aqui. A constante K é incluída porque leva tempo para a função alocar ou desalocar memória para uma variável ou executar uma operação matemática. Usamos K para definir o tempo, pois é muito minuto e insignificante.
• A complexidade de tempo deste programa recursivo pode ser simplesmente calculada já que, no pior cenário, o método doSomething() é chamado n vezes. Formalmente falando, a complexidade temporal da função é O(N).

Recursão em árvore

• Quando você faz uma chamada recursiva em seu caso recursivo mais de uma vez, isso é chamado de recursão em árvore. Uma ilustração eficaz da recursão em árvore é a sequência de Fibonacci. As funções recursivas em árvore operam em tempo exponencial; eles não são lineares em sua complexidade temporal.
• Dê uma olhada no pseudocódigo abaixo,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• A única diferença entre este código e o anterior é que este faz mais uma chamada para a mesma função com valor menor de n.
• Vamos colocar T(n) = T(n-1) + T(n-2) + k como a relação de recorrência para esta função. K serve como constante mais uma vez.
• Quando mais de uma chamada para a mesma função com valores menores é realizada, esse tipo de recursão é conhecido como recursão em árvore. O aspecto intrigante agora é: quão demorada é essa função?
• Faça uma estimativa com base na árvore de recursão abaixo para a mesma função.
  
• Pode ocorrer que seja um desafio estimar a complexidade do tempo olhando diretamente para uma função recursiva, especialmente quando se trata de uma recursão em árvore. O Método da Árvore Recursiva é uma das várias técnicas para calcular a complexidade temporal de tais funções. Vamos examiná-lo com mais detalhes.

O que é o método da árvore de recursão?

• Relações de recorrência como T(N) = T(N/2) + N ou as duas que abordamos anteriormente na seção de tipos de recursão são resolvidas usando a abordagem da árvore de recursão. Estas relações de recorrência utilizam frequentemente uma estratégia de dividir para conquistar para resolver problemas.
• Leva tempo para integrar as respostas aos subproblemas menores que são criados quando um problema maior é dividido em subproblemas menores.
• A relação de recorrência, por exemplo, é T(N) = 2 * T(N/2) + O(N) para a classificação Merge. O tempo necessário para combinar as respostas a dois subproblemas com um tamanho combinado de T(N/2) é O(N), o que também se aplica ao nível de implementação.
• Por exemplo, como a relação de recorrência para pesquisa binária é T(N) = T(N/2) + 1, sabemos que cada iteração da pesquisa binária resulta em um espaço de pesquisa que é cortado pela metade. Assim que o resultado for determinado, saímos da função. A relação de recorrência tem +1 adicionado porque esta é uma operação de tempo constante.
• A relação de recorrência T(n) = 2T(n/2) + Kn deve ser considerada. Kn denota a quantidade de tempo necessária para combinar as respostas a subproblemas n/2-dimensionais.
• Vamos representar a árvore de recursão para a relação de recorrência mencionada.

Podemos tirar algumas conclusões do estudo da árvore de recursão acima, incluindo

1. A magnitude do problema em cada nível é tudo o que importa para determinar o valor de um nó. O tamanho do problema é n no nível 0, n/2 no nível 1, n/2 no nível 2 e assim por diante.

2. Em geral, definimos a altura da árvore como igual ao log (n), onde n é o tamanho da questão, e a altura desta árvore de recursão é igual ao número de níveis da árvore. Isso é verdade porque, como acabamos de estabelecer, a estratégia de dividir e conquistar é usada por relações de recorrência para resolver problemas, e passar do problema de tamanho n para o problema de tamanho 1 requer simplesmente realizar log(n) passos.

• Considere o valor de N = 16, por exemplo. Se pudermos dividir N por 2 em cada etapa, quantas etapas serão necessárias para obter N = 1? Considerando que estamos dividindo por dois a cada passo, a resposta correta é 4, que é o valor de log(16) base 2.

log(16) base 2

log(2^4) base 2

arquitetura linux

4 * log(2) base 2, já que log(a) base a = 1

então, 4 * log(2) base 2 = 4

3. Em cada nível, o segundo termo da recorrência é considerado a raiz.

Embora a palavra “árvore” apareça no nome desta estratégia, você não precisa ser um especialista em árvores para compreendê-la.

Como usar uma árvore de recursão para resolver relações de recorrência?

O custo do subproblema na técnica da árvore recursiva é a quantidade de tempo necessária para resolver o subproblema. Portanto, se você notar a frase “custo” vinculada à árvore de recursão, ela simplesmente se refere à quantidade de tempo necessária para resolver um determinado subproblema.

Vamos entender todas essas etapas com alguns exemplos.

Exemplo

Considere a relação de recorrência,

T(n) = 2T(n/2) + K

bourne novamente concha

Solução

A relação de recorrência fornecida mostra as seguintes propriedades,

Um problema de tamanho n é dividido em dois subproblemas, cada um de tamanho n/2. O custo de combinar as soluções para estes subproblemas é K.

Cada problema de tamanho n/2 é dividido em dois subproblemas, cada um de tamanho n/4 e assim por diante.

No último nível, o tamanho do subproblema será reduzido para 1. Em outras palavras, finalmente atingimos o caso base.

Vamos seguir os passos para resolver esta relação de recorrência,

Etapa 1: desenhe a árvore de recursão

Passo 2: Calcule a Altura da Árvore

Como sabemos que quando dividimos continuamente um número por 2, chega um momento em que esse número é reduzido a 1. Assim como no problema de tamanho N, suponha que após K divisões por 2, N se torne igual a 1, o que implica, ( n / 2^k) = 1

Aqui n/2^k é o tamanho do problema no último nível e é sempre igual a 1.

Agora podemos calcular facilmente o valor de k da expressão acima, levando log() para ambos os lados. Abaixo está uma derivação mais clara,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) /log(2)
• k = log (n) base 2

Portanto, a altura da árvore é log (n) base 2.

Etapa 3: Calcule o custo em cada nível

• Custo no Nível-0 = K, dois subproblemas são mesclados.
• Custo no Nível 1 = K + K = 2*K, dois subproblemas são mesclados duas vezes.
• Custo no Nível 2 = K + K + K + K = 4*K, dois subproblemas são mesclados quatro vezes. e assim por diante....

Etapa 4: Calcule o número de nós em cada nível

Vamos primeiro determinar o número de nós no último nível. Da árvore de recursão, podemos deduzir isso

• Nível 0 tem 1 (2 ^ 0) nó
• Nível 1 tem 2 (2 ^ 1) nós
• O nível 2 tem 4 (2 ^ 2) nós
• Nível 3 tem 8 (2 ^ 3) nós

Portanto, o nível log(n) deve ter 2^(log(n)) nós, ou seja, n nós.

Passo 5: Some o custo de todos os níveis

• O custo total pode ser escrito como,
• Custo Total = Custo de todos os níveis, exceto o último nível + Custo do último nível
• Custo total = Custo para o nível 0 + Custo para o nível 1 + Custo para o nível 2 +.... + Custo para o nível-log(n) + Custo para o último nível

O custo do último nível é calculado separadamente porque é o caso base e nenhuma fusão é feita no último nível, portanto, o custo para resolver um único problema neste nível é um valor constante. Vamos considerar como O (1).

Vamos colocar os valores nas fórmulas,

• T(n) = K + 2*K + 4*K + .... + log(n)` vezes + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) vezes)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) vezes + O(n)

Se você observar atentamente a expressão acima, ela forma uma progressão geométrica (a, ar, ar^2, ar^3 ...... tempo infinito). A soma de GP é dada por S(N) = a / (r - 1). Aqui está o primeiro termo e r é a razão comum.