No mundo da ciência da computação, a recursão é um método onde a solução de um problema depende de instâncias menores do mesmo problema. É um processo no qual uma função chama a si mesma como uma sub-rotina. Isto permite que a função seja chamada com menos argumentos, reduzindo a quantidade de informações de estado que precisam ser mantidas pela função e fornecendo um meio muito elegante e conciso de expressar soluções para alguns tipos de problemas. A recursão é frequentemente vista como um conceito desafiador para iniciantes. No entanto, quando compreendido corretamente, pode ser uma ferramenta extremamente poderosa no arsenal de um programador. Ele 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, aplicaremos 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-1) e (n-2) números.

Visualizações recursivas no SmartPy

No SmartPy, a recursão é implementada permitindo que uma função chame a si mesma dentro de 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 visualização é uma função SmartPy que não modifica o armazenamento do contrato, mas pode lê-lo. Quando falamos sobre uma visão recursiva, queremos dizer uma função de visão que chama a si mesma durante 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, começando em 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. Isso significa que para obter o n-ésimo número na sequência de Fibonacci, adicionamos o (n-1)-ésimo e o (n-2)-ésimo número. Essa natureza recursiva é exatamente o que torna a sequência de Fibonacci perfeita para a compreensão da recursão. Agora que entendemos melhor a 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 entender como funções recursivas são criadas e usadas no SmartPy.

Python 
 import smartpy as sp 


 @sp.module 
 def main(): 
 class FibonacciView(sp.Contract): 
 """Contrato com uma visão recursiva para calcular a soma dos números de Fibonacci."""

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

            Args: 
 n (sp.int): número de números de Fibonacci a serem somados.
            Retorno: 
 (sp.int): a soma dos números de Fibonacci 
 """ 
 sp.cast(n, int) 
 se n < 2: 
 return n 
 else: 
 n1 = sp.view("fibonacci", sp.self_address(), n - 1, int).unwrap_some() 
 n2 = sp.view("fibonacci", sp.self_address(), n - 2, int).unwrap_some()
                retorne n1 + n2 


 se "modelos" não estiverem em __name__: 

 @sp.add_test(name="FibonacciView cenário básico", is_default=True) 
 def basic_scenario(): 
 sc = sp.test_scenario(main)
        sc.h1("Cenário básico.")
        sc.h2("Origem.")
        c1 = main.FibonacciView() 
 sc += c1 
 sc.verify(c1.fibonacci(8) == 21)

Este contrato FibonacciView possui uma função de visualização recursiva, fibonacci, que retorna o enésimo número de Fibonacci.

A função é decorada com @sp.onchain_view(), indicando que esta é uma operação somente 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 convertemos n em 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 fibonacci para n-1 e n-2 e, em seguida, adicionando os resultados. Isto corresponde à relação de recorrência que define a sequência de Fibonacci. As chamadas sp.view criam essas chamadas recursivas para a própria função fibonacci .

Usando um Loop para Eficiência 
 Embora a recursão seja um conceito valioso para compreensão, é importante observar que ela pode ser menos eficiente e exigir mais recursos computacionais, especialmente quando se lida com números grandes. Para evitar problemas como estouro de pilha, uma abordagem mais eficiente seria usar um loop para calcular a Sequência de Fibonacci e armazenar os números de Fibonacci calculados em um contrato separado.
Aqui está um exemplo de alto nível de como você pode modificar o contrato FibonacciView para usar um loop: 
 Este contrato modificado, FibonacciCalculator, usa um loop para calcular com eficiência os números de Fibonacci e os armazena no armazenamento do contrato. Você pode então chamar o ponto de entrada calcula_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(): 
 class FibonacciCalculator(sp.Contract): 
 """Contrato para calcular eficientemente a sequência de Fibonacci."""def __init__(self): 
 self.init(storage=sp.map(tkey=sp.TInt, tvalue=sp.TInt).set(0, 0).set(1, 1)) 

 @sp.entry_pointdef calcule_fibonacci(self, n): 
 sp.verify(n >= 0, message="n deve ser não negativo") 
 storage = self.data 
 para i no intervalo (2, n + 1): 
 next_fib = armazenamento[i - 1] + armazenamento[i - 2] 
 armazenamento = storage.set(i, next_fib) 
 sp.result(armazenamento[n])

Vamos continuar com a seção de testes.

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

Executando 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”. Você deverá ver o cenário de teste sendo executado no lado direito do IDE. Você verá as operações sendo realizadas e as verificações sendo verificadas.
   Esta lição cobriu muito terreno. Passamos do básico da recursão e como ela é usada na programação, até visualizações recursivas no SmartPy, e até mesmo aplicando esses conceitos à sequência de Fibonacci. Também exploramos um exemplo de código funcional no SmartPy e você aprendeu como executar e verificar esse código no SmartPy IDE.