🎯 O mapa da aula

• Entender como variáveis ocupam a memória e como ponteiros guardam endereços.
• Usar vetores e ponteiros com segurança.
• Alocar e liberar memória com new/delete e conhecer malloc/free.
• Comparar busca linear, busca linear em vetor ordenado e busca binária.
• Construir e acompanhar funções recursivas usando uma pilha de execução.

🧠 Variáveis vivem na memória

Uma variável possui um valor, um tipo, um tamanho e um endereço.

int numero = 25;

cout << numero << endl;   // valor
cout << &numero << endl;  // endereço, por exemplo 0x7ffd...

📍 O que é um ponteiro?

Um ponteiro é uma variável que armazena o endereço de outra variável.

int numero = 20;
int* ptrNumero = №

cout << ptrNumero << endl;   // endereço de numero
cout << *ptrNumero << endl;  // valor guardado nesse endereço

🔁 Indireção: alterar por meio do endereço

O ponteiro não cria uma cópia de numero. Ele oferece outro caminho até a mesma variável.

int numero = 5;
int* p = №

cout << *p << endl;  // 5
*p = 8;                // altera numero por indireção
cout << numero << endl; // 8

🧩 Três declarações que parecem iguais

int* p;

int *p;

int* p, q;

int *p1, *p2; // os dois são ponteiros
int* p3, p4;  // p3 é ponteiro; p4 é inteiro

🔢 Vetores e ponteiros

Em muitas expressões, o nome de um vetor representa o endereço do seu primeiro elemento. O vetor não deixa de ser um vetor: ele apenas pode ser acessado por outro caminho.

int vetor[3] = {10, 20, 30};
int* p = vetor; // equivalente a &vetor[0]

cout << vetor[1] << endl; // 20
cout << p[1] << endl;     // 20
cout << *(p + 1) << endl; // 20

↔️ Ponteiros em funções

Passar um ponteiro copia o endereço, mas permite alterar a variável original por indireção.

void dobro(int* valor) {
    if (valor != nullptr)
        *valor = 2 * (*valor);
}

int n = 7;
dobro(&n);
cout << n; // 14

📦 Ponteiros para registros

Quando um ponteiro aponta para uma estrutura, o operador -> acessa diretamente seus campos.

struct Ponto {
    int x, y;
};

Ponto p1{3, 4};
Ponto* ptr = &p1;

cout << p1.x << endl;
cout << (*ptr).y << endl;
cout << ptr->x << endl; // forma mais legível

🛡️ Ponteiro nulo é diferente de ponteiro válido

int* p = nullptr;

if (p != nullptr) {
    cout << *p;
} else {
    cout << "Ainda não aponta para um dado";
}

🧹 Vazamento e ponteiro pendente

int* p = new int(10);
int* copia = p;

delete p;
p = nullptr;
// copia ainda guarda o endereço liberado: ponteiro pendente

✅ Regras de segurança

• Inicialize com nullptr ou com o endereço de uma variável válida.
• Teste o ponteiro antes de desreferenciar quando ele puder ser nulo.
• Não acesse índices fora dos limites.
• Use delete para um objeto e delete[] para um vetor.
• Depois de liberar, atribua nullptr ao ponteiro principal.
• Defina claramente quem aloca e quem libera a memória.

🗂️ Alocação automática × dinâmica

❓ Por que não usar simplesmente VLA?

int tam;
cin >> tam;
int vetor[tam]; // parece resolver...

Essa declaração é conhecida como VLA (variable-length array).

✅ O que usar no lugar do VLA?

int tam;
cin >> tam;

if (tam > 0) {
    int* vetor = new int[tam];
    // use vetor[0] até vetor[tam - 1]
    delete[] vetor;
    vetor = nullptr;
}

🧭 Alocação dinâmica de um elemento

int* ptr = new int;
*ptr = 13;

cout << *ptr << endl;

delete ptr;
ptr = nullptr;

📦 Alocação dinâmica de vetor

int n;
cin >> n;

int* vetor = new int[n];
for (int i = 0; i < n; i++)
    cin >> vetor[i];

cout << vetor[0];
delete[] vetor;
vetor = nullptr;

🆚 new/delete e malloc/free

int* v = new int[n];
delete[] v;

int* v = static_cast<int*>(
    malloc(n * sizeof(int)));
free(v);

🧰 Como funciona malloc()?

#include <cstdlib>

int n;
cin >> n;

int* vetor = static_cast<int*>(
    malloc(n * sizeof(int))
);

if (vetor == nullptr) {
    cout << "Falha na alocação";
} else {
    vetor[0] = 42;
    free(vetor);
    vetor = nullptr;
}

• sizeof(int) informa quantos bytes um inteiro ocupa.
• malloc retorna um endereço bruto, convertido para int*.
• free devolve o bloco ao sistema.

🧪 Qual escolher?

🔎 O problema de busca em vetores

Dado um vetor V e uma chave K, queremos saber se K aparece e em qual índice.

V = {2, -3, 101, 104, 0, 1, 2, 3, -3, 0}
K = 104

// resposta: encontrado no índice 3

🔍 Busca linear: comparar um por um

int buscaLinear(const int v[], int n, int chave) {
    for (int i = 0; i < n; i++) {
        if (v[i] == chave)
            return i;
    }
    return -1;
}

• Melhor caso: a chave está na primeira posição.
• Pior caso: a chave está na última posição ou não aparece.
• Não exige vetor ordenado.

⏩ Busca linear com parada antecipada

Se o vetor estiver ordenado, ainda podemos evitar comparações depois que o valor atual ultrapassa a chave.

int i = 0;
while (i < n and v[i] < chave)
    i++;

if (i < n and v[i] == chave)
    return i;
return -1;

⚡ Busca binária: metade por vez

A busca binária exige um vetor ordenado e mantém apenas o intervalo onde a chave ainda pode estar.

1. Calcule o índice do meio.
2. Compare chave com v[meio].
3. Se a chave for menor, descarte a metade direita.
4. Se for maior, descarte a metade esquerda.
5. Repita até encontrar ou o intervalo ficar vazio.

🔁 Por que usar recursão?

Recursão é quando uma função chama a si mesma para resolver uma versão menor do mesmo problema.

problema grande
→ resolve um problema menor
→ resolve um problema ainda menor
→ caso base
→ retorna os resultados

📐 Relação de recorrência: fatorial

A matemática já descreve o fatorial de forma recursiva:

4! = 4 × 3 × 2 × 1 × 1 = 24

🧩 Função recursiva do fatorial

int fatorial(int n) {
    if (n == 0)          // caso base
        return 1;
    return n * fatorial(n - 1); // caso geral
}

1️⃣ Fatorial(4): primeira chamada

fatorial(4)

return 4 * fatorial(3);

A função ainda não retorna 24: ela precisa descobrir o resultado de fatorial(3).

2️⃣ Fatorial(3): segunda chamada

fatorial(4)
  fatorial(3)

4 * (3 * fatorial(2))

A chamada de número 3 é criada antes de qualquer produto ser finalizado.

3️⃣ Fatorial(2): terceira chamada

fatorial(4)
  fatorial(3)
    fatorial(2)

4 * (3 * (2 * fatorial(1)))

4️⃣ Fatorial(1): quarta chamada

fatorial(4)
  fatorial(3)
    fatorial(2)
      fatorial(1)

4 * (3 * (2 * (1 * fatorial(0))))

A próxima chamada será fatorial(0), o caso base.

🛑 Fatorial(0): caso base

fatorial(4)
  fatorial(3)
    fatorial(2)
      fatorial(1)
        fatorial(0)

4 * (3 * (2 * (1 * fatorial(0))))

↩️ Retorno: fatorial(0)

fatorial(4)
  fatorial(3)
    fatorial(2)
      fatorial(1)

4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))

↩️ Desempilhar: fatorial(1)

fatorial(4)
  fatorial(3)
    fatorial(2)

4 * (3 * (2 * 1))
= 4 * (3 * 2)

↩️ Desempilhar: fatorial(2)

fatorial(4)
  fatorial(3)

4 * (3 * 2)
= 4 * 6

↩️ Desempilhar: fatorial(3)

fatorial(4)

4 * 6
= 24

✅ Desempilhar: fatorial(4)

vazia

4 * 6
= 24

🌳 Árvore e pilha de recursão

fatorial(4)
└─ fatorial(3)
   └─ fatorial(2)
      └─ fatorial(1)
         └─ fatorial(0)

🧠 Recursão: erros que aparecem nos testes

int f(int n) {
    return f(n - 1);
}

int f(int n) {
    if (n == 0) return 1;
    return f(n);
}

🆚 Recursão e repetição

int fatorial(int n) {
    if (n == 0) return 1;
    return n * fatorial(n - 1);
}

int resultado = 1;
for (int i = 2; i <= n; i++)
    resultado *= i;

🧩 Busca binária recursiva

int buscaBinaria(const int v[], int inicio, int fim, int chave) {
    if (inicio > fim)
        return -1; // intervalo vazio

    int meio = (inicio + fim) / 2;
    if (v[meio] == chave)
        return meio;
    if (chave < v[meio])
        return buscaBinaria(v, inicio, meio - 1, chave);
    return buscaBinaria(v, meio + 1, fim, chave);
}

🎞️ Busca binária recursiva: pilha

Vetor: {1, 4, 5, 10, 16, 19, 20, 27, 30} · chave: 27.

busca(0, 8)
→ busca(5, 8)
→ busca(7, 8)
→ encontra em 7

meio = 4 → 16
meio = 6 → 20
meio = 7 → 27

🧪 Teste de mesa: escreva a execução

Para conferir uma busca binária recursiva, registre uma linha por chamada.

🧩 Prática orientada

1. Alocar dinamicamente um vetor de n inteiros.
2. Ler os valores em ordem crescente.
3. Ler uma chave e executar busca binária iterativa.
4. Repetir usando uma função recursiva.
5. Registrar em uma tabela cada valor de inicio, fim e meio.
6. Liberar o vetor com delete[].