Lição 5

Compreendendo visualizações recursivas com Fibonacci

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.

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.

Isenção de responsabilidade
* O investimento em criptomoedas envolve grandes riscos. Prossiga com cautela. O curso não se destina a servir de orientação para investimentos.
* O curso foi criado pelo autor que entrou para o Gate Learn. As opiniões compartilhadas pelo autor não representam o Gate Learn.
Catálogo
Lição 5

Compreendendo visualizações recursivas com Fibonacci

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.

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.

Isenção de responsabilidade
* O investimento em criptomoedas envolve grandes riscos. Prossiga com cautela. O curso não se destina a servir de orientação para investimentos.
* O curso foi criado pelo autor que entrou para o Gate Learn. As opiniões compartilhadas pelo autor não representam o Gate Learn.
It seems that you are attempting to access our services from a Restricted Location where Gate is unable to provide services. We apologize for any inconvenience this may cause. Currently, the Restricted Locations include but not limited to: the United States of America, Canada, Cambodia, Thailand, Cuba, Iran, North Korea and so on. For more information regarding the Restricted Locations, please refer to the User Agreement. Should you have any other questions, please contact our Customer Support Team.