Exercícios Resolvidos de Introdução à recursividade

Ver Teoria

Enunciado

Identifique em uma função recursiva que, dado dois números inteiros x e n , calcula o valor de x n o caso básico e os passos de recursão que devem ser utilizados.

Passo 1

Para descobrirmos o caso básico temos que pensar como podemos subdividir um problema de potência e onde essas divisões devem parar.

Usando como exemplo a potência 2 5 podemos dizer que isso é igual a 2 * 2 4 , que por sua vez é igual a 2 * 2 * 2 3 .

Tá, mas aonde queremos chegar?

No caso mais trivial possível que é: 2 * 2 * 2 * 2 * 2 * 2 0 . Ou seja, temos uma solução simples quando o problema é subdividido a x 0 = 1 ou nesse caso 2 0 = 1 e por esse motivo esse é o nosso caso básico.

Passo 2

O passo de recursão, por sua vez, é a forma como vamos subdividir o problema para atingir problemas cada vez menores.

Mas calma, nós não já descobrimos isso?

Logo, podemos dizer que o passo de recursão utilizado foi x n = x * x n - 1 que passando para o nosso exemplo daria algo mais ou menos assim: 2 5 = 2 * 2 5 - 1 .

Resposta

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