No mundo da ciência da computação, a recursão é um método em que a solução para um problema depende de instâncias menores do mesmo problema. É um processo em que uma função se autodenomina como uma sub-rotina. Isso permite que a função seja chamada com menos argumentos, reduzindo a quantidade de informação de estado que precisa ser mantida pela função e fornecendo um meio muito elegante e conciso de expressar soluções para alguns tipos de problemas. A recursão é muitas vezes vista como um conceito desafiador para os iniciantes compreenderem. No entanto, quando compreendido corretamente, pode ser uma ferramenta extremamente poderosa no arsenal de um programador. Pode ajudar a criar um código mais limpo e conciso, e muitas vezes pode ser usado para resolver problemas complexos com soluções simples e elegantes.

Nesta lição, vamos aplicar recursão à sequência de Fibonacci, que é uma série de números onde um número é a adição dos dois últimos números, ou seja, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 e assim por diante. A sequência começa em 0 e, portanto, o enésimo número é a soma dos números (n-1) e (n-2).

Visualizações Recursivas no SmartPy

No SmartPy, a recursão é implementada permitindo que uma função se chame dentro da sua própria definição. Este método é extremamente útil ao lidar com problemas que podem ser divididos em subproblemas menores e idênticos. Uma visão recursiva no SmartPy é essencialmente uma visão que usa recursão. Uma vista é uma função SmartPy que não modifica o armazenamento do contrato mas pode ler a partir dele. Quando falamos de uma visão recursiva, queremos dizer uma função de visualização que se chama durante a sua execução.

Sequência de Fibonacci

A sequência de Fibonacci é um conjunto de números onde cada número é a soma dos dois anteriores, a partir de 0 e 1. Esta sequência, embora simples, fornece uma excelente base para a compreensão da recursão devido à sua natureza recursiva.

A sequência de Fibonacci é definida pela relação de recorrência:

SCSS
F (n) = F (n-1) + F (n-2)

Com as condições iniciais sendo F (0) = 0 e F (1) = 1. Isto significa que para obter o n-ésimonúmero na sequência de Fibonacci, adicionamos o (n-1) -ésimo e o (n-2) -ésimo número. Esta natureza recursiva é exatamente o que torna a sequência de Fibonacci perfeita para compreender a recursão. Agora que temos uma melhor compreensão da recursão e como ela se aplica à sequência de Fibonacci, vamos mergulhar no código SmartPy que implementa uma visão recursiva para calcular a sequência de Fibonacci.

Passo a passo do código

O código SmartPy fornecido define um contrato, FibonacciView, que calcula a sequência de Fibonacci usando uma visão recursiva. Este é um ótimo exemplo para perceber como as funções recursivas são criadas e utilizadas no SmartPy.

Python
importar smartpy como sp


@sp .módulo
def principal ():
 classe FibonacciView (SP.Contract):
 """Contrato com uma visão recorrente para calcular a soma dos números de Fibonacci. """

        @sp .onchain_view ()
 def fibonacci (self, n):
 """Devolver a soma dos números de Fibonacci até n.

            Args:
 n (sp.int): número de números de fibonacci a somatório.
            Retorno:
 (sp.int): a soma dos números de Fibonacci
 """
 sp.cast (n, int)
 se n < 2:
 voltar n
 caso contrário:
 n1 = sp.view (fibonacci, " " sp.self_address (), n - 1, int) .unwrap_some ()
 n2 = sp.view (fibonacci, " " sp.self_address (), n - 2, int) .unwrap_some ()
                retorno n1+ n2


se " os modelos " não estiverem em __name__:

 @sp .add_test (nome= " FibonacciVer cenário básico, is_default=true) "
 def basic_scenario ():
 sc = sp.test_scenario (principal)
        sc.h1 ("Cenário básico. ")
        sc.h2 (Origem. " ")
        c1 = Main.FibonacciView ()
 sc += c1
 sc.verify (c1.fibonacci (8) == 21)

Este contrato do FibonacciView tem uma função de visão recursiva, fibonacci, que devolve o enésimo número de Fibonacci.

A função está decorada com @sp.onchain_view (), indicando que esta é uma operação só de leitura no armazenamento do contrato. Esta função recebe um inteiro n como argumento, representando a posição na sequência de Fibonacci que queremos recuperar.

Dentro da função, primeiro lançamos n para um número inteiro por segurança. A parte recursiva da função vem a seguir. Se n for menor que 2, simplesmente retornamos n porque os dois primeiros números da sequência de Fibonacci são 0 e 1. Se n for maior ou igual a 2, calculamos o enésimo número de Fibonacci chamando recursivamente a função de fibonacci para n-1 e n-2 e adicionando os resultados. Isto corresponde à relação de recorrência que define a sequência de Fibonacci. As chamadas sp.view criam estas chamadas recursivas para a própria função fibonacci.

Utilizar um Loop para a Eficiência
Embora a recursão seja um conceito valioso para a compreensão, é importante notar que pode ser menos eficiente e exigir mais recursos computacionais, especialmente quando se lida com números grandes. Para evitar problemas como stack overflow, uma abordagem mais eficiente seria usar um loop para calcular a sequência de Fibonacci e armazenar os números de Fibonacci calculados num contrato separado.
Aqui está um exemplo de alto nível de como pode modificar o contrato FibonacciView para usar um loop:
Este contrato modificado, FibonaccicalCulator, usa um loop para calcular eficientemente os números de Fibonacci e armazena-os no armazenamento do contrato. Pode então ligar para o ponto de entrada calculate_fibonacci para recuperar o enésimo número de Fibonacci.
Esta abordagem é mais eficiente em termos de recursos e adequada para valores maiores de n.

Python
@sp .moduledef main ():
 classe FibonaccicCalculator (SP.Contract):
 """Contrato para calcular eficientemente a sequência de Fibonacci. """def __init__(auto):
 self.init (storage=sp.map (tKey=sp.tint, TValue=sp.tint) .set (0, 0) .set (1, 1))

 @sp .entry_pointdef calculate_fibonacci (self, n):
 sp.verify (n > = 0, mensagem= " n deve ser não negativo) "
 armazenamento = auto.dados
 para i no alcance (2, n + 1):
 next_fib = armazenamento [i - 1] + armazenamento [i - 2]
 armazenamento = storage.set (i, next_fib)
 sp.resultado (armazenamento [n])

Vamos continuar com a secção de testes.

Na função de teste basic_scenario, criamos uma nova instância do contrato FibonacciView, adicionamos ao nosso cenário e usamos sc.verify para verificar se o 8º número de Fibonacci é 21, o que é verdade para a sequência de Fibonacci.

Executar o código no SmartPy IDE

Para executar o código:

1. Abra o IDE SmartPy.

2. Copie e cole o código fornecido no editor.

3. Clique no botão “Executar”. Deverá ver o cenário de teste a ser executado no lado direito do IDE. Verá as operações a serem realizadas e as verificações a serem verificadas.
   Esta lição cobriu muito terreno. Passamos do básico da recursão e como ela é usada na programação, para visualizações recursivas no SmartPy e até aplicamos esses conceitos à sequência de Fibonacci. Também explorámos um exemplo de código funcional no SmartPy e aprendeu a executar e verificar este código no SmartPy IDE.