---
title: "Fibonacci (Programação Dinâmica) em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/fibonacci-programa%C3%A7%C3%A3o-din%C3%A2mica-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/fibonacci-programa%C3%A7%C3%A3o-din%C3%A2mica-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda a calcular Fibonacci com programação dinâmica em Zig. Memoização, tabulação, código funcional e análise de complexidade."
date: "2026-02-21"
author: "Zig Brasil"
---

# Fibonacci (Programação Dinâmica) em Zig — Implementação e Explicação

Aprenda a calcular Fibonacci com programação dinâmica em Zig. Memoização, tabulação, código funcional e análise de complexidade.


# Fibonacci (Programação Dinâmica) em Zig — Implementação e Explicação

A **sequência de Fibonacci** é uma das sequências mais famosas da matemática: cada número é a soma dos dois anteriores. A abordagem ingênua recursiva tem complexidade exponencial O(2^n), mas com **programação dinâmica** podemos reduzi-la para O(n).

## Como Funciona

A sequência começa com F(0) = 0, F(1) = 1, e para n >= 2: F(n) = F(n-1) + F(n-2).

### Abordagens

1. **Top-Down (Memoização)**: recursão com cache dos resultados já calculados
2. **Bottom-Up (Tabulação)**: preenche uma tabela iterativamente de baixo para cima
3. **Espaço Otimizado**: mantém apenas os dois últimos valores

### Visualização

```
Recursão ingênua para F(5) — muitas chamadas repetidas:
                    F(5)
                   /    \
                F(4)     F(3)
               /    \    /   \
            F(3)   F(2) F(2) F(1)
           /   \   / \   / \
         F(2) F(1) F(1) F(0) F(1) F(0)
         / \
       F(1) F(0)

Com programação dinâmica (tabulação):
  i:    0   1   2   3   4   5
  F[i]: 0   1   1   2   3   5
              ↑       ↑
              |       |
        F[2]=F[1]+F[0]  F[4]=F[3]+F[2]

Espaço otimizado — apenas dois valores:
  prev=0, curr=1
  → prev=1, curr=0+1=1   (F(2)=1)
  → prev=1, curr=1+1=2   (F(3)=2)
  → prev=2, curr=1+2=3   (F(4)=3)
  → prev=3, curr=2+3=5   (F(5)=5)
```

## Implementação em Zig

```zig
const std = @import("std");
const Allocator = std.mem.Allocator;

/// Fibonacci ingênuo — O(2^n) — apenas para comparação
pub fn fibRecursivo(n: u64) u64 {
    if (n <= 1) return n;
    return fibRecursivo(n - 1) + fibRecursivo(n - 2);
}

/// Fibonacci com memoização (top-down) — O(n) tempo, O(n) espaço
pub fn fibMemoizado(n: u64, allocator: Allocator) !u64 {
    if (n <= 1) return n;

    const tamanho: usize = @intCast(n + 1);
    const memo = try allocator.alloc(?u64, tamanho);
    defer allocator.free(memo);
    @memset(memo, null);
    memo[0] = 0;
    memo[1] = 1;

    return fibMemoHelper(n, memo);
}

fn fibMemoHelper(n: u64, memo: []?u64) u64 {
    const idx: usize = @intCast(n);
    if (memo[idx]) |valor| return valor;

    const resultado = fibMemoHelper(n - 1, memo) + fibMemoHelper(n - 2, memo);
    memo[idx] = resultado;
    return resultado;
}

/// Fibonacci com tabulação (bottom-up) — O(n) tempo, O(n) espaço
pub fn fibTabulacao(n: u64, allocator: Allocator) !u64 {
    if (n <= 1) return n;

    const tamanho: usize = @intCast(n + 1);
    const tabela = try allocator.alloc(u64, tamanho);
    defer allocator.free(tabela);

    tabela[0] = 0;
    tabela[1] = 1;

    var i: usize = 2;
    while (i <= n) : (i += 1) {
        tabela[i] = tabela[i - 1] + tabela[i - 2];
    }

    return tabela[@intCast(n)];
}

/// Fibonacci com espaço otimizado — O(n) tempo, O(1) espaço
pub fn fibOtimizado(n: u64) u64 {
    if (n <= 1) return n;

    var prev: u64 = 0;
    var curr: u64 = 1;
    var i: u64 = 2;
    while (i <= n) : (i += 1) {
        const proximo = prev + curr;
        prev = curr;
        curr = proximo;
    }
    return curr;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    try stdout.print("Sequência de Fibonacci (primeiros 20 termos):\n", .{});
    for (0..20) |i| {
        try stdout.print("F({d}) = {d}\n", .{ i, fibOtimizado(@intCast(i)) });
    }

    // Comparação de métodos
    const n: u64 = 40;
    try stdout.print("\nF({d}) com tabulação: {d}\n", .{ n, try fibTabulacao(n, allocator) });
    try stdout.print("F({d}) com memoização: {d}\n", .{ n, try fibMemoizado(n, allocator) });
    try stdout.print("F({d}) otimizado: {d}\n", .{ n, fibOtimizado(n) });
}
```

## Análise de Complexidade

| Método | Tempo | Espaço |
|--------|-------|--------|
| **Recursivo ingênuo** | O(2^n) | O(n) pilha |
| **Memoização (top-down)** | O(n) | O(n) |
| **Tabulação (bottom-up)** | O(n) | O(n) |
| **Espaço otimizado** | O(n) | O(1) |
| **Exponenciação de matriz** | O(log n) | O(1) |

## Quando Usar Cada Abordagem

- **Memoização**: quando nem todos os subproblemas precisam ser resolvidos
- **Tabulação**: quando a ordem dos subproblemas é clara e todos são necessários
- **Espaço otimizado**: quando só precisa do resultado final, não de toda a sequência
- **Matriz**: quando n é extremamente grande (veja [Fibonacci por Matriz](/algoritmos/fibonacci-matrix/))

## Perguntas Frequentes

**Por que a versão recursiva ingênua de Fibonacci é tão lenta?**

A versão recursiva ingênua recalcula os mesmos subproblemas repetidas vezes. Para calcular `F(5)`, ela calcula `F(3)` duas vezes, `F(2)` três vezes, e assim por diante. O número de chamadas cresce exponencialmente — para `F(40)`, são mais de um bilhão de chamadas. A programação dinâmica elimina esse problema armazenando os resultados já calculados, fazendo cada subproblema ser resolvido apenas uma vez. Em Zig, isso fica claro porque você vê exatamente onde a memória é alocada para o cache (o slice `memo`), tornando o comportamento completamente transparente.

**Qual a diferença prática entre memoização e tabulação em Zig?**

Memoização (top-down) parte do problema maior e resolve subproblemas conforme necessário — útil quando nem todos os subproblemas precisam ser calculados. Tabulação (bottom-up) resolve todos os subproblemas em ordem crescente — geralmente mais eficiente em cache de CPU por ter acesso sequencial à memória. A versão com espaço otimizado em Zig usa apenas duas variáveis `prev` e `curr`, eliminando a necessidade de alocar memória e sendo ideal quando se precisa apenas do resultado final sem armazenar toda a sequência.

## Recursos Relacionados

- [Fibonacci por Exponenciação de Matriz](/algoritmos/fibonacci-matrix/) — Fibonacci em O(log n)
- [Exponenciação Rápida](/algoritmos/exponenciacao-rapida/) — Base para Fibonacci matricial
- [Knapsack (Mochila)](/algoritmos/knapsack-mochila/) — Outro problema clássico de DP
- [LCS — Subsequência Comum](/algoritmos/lcs-subsequencia-comum/) — DP com duas sequências