Recursividad

Introducción

La recursividad consiste en definir una función en términos de sí misma.
Siempre necesitamos:

• Caso base: condición de parada.
• Caso recursivo: reduce el problema (tamaño menor) y llama de nuevo.

En P1 (C) la idea se practica mucho con:

• arrays + índice n (último elemento a procesar),
• números (dividir entre 10),
• cadenas ('\0' como fin).

En P2 (C++) es lo mismo, pero solemos:

• usar std::vector<int> o std::string,
• pasar por const& para evitar copias,
• usar std::size_t para índices (aunque en recursividad a veces es más cómodo int para permitir -1).

Para no repetir patrones, seleccionamos 4 ejercicios representativos: arrays, “comprobación”, número, y cadenas.

---

1) Suma de un vector (recursiva con n = último índice)

P1 — C

int sumaVector(int v[], int n) {
    int res;

    if (n == 0) {
        res = v[0];
    } else {
        res = v[n] + sumaVector(v, n - 1);
    }
    return res;
}

P2 — C++

#include <vector>

int sumaVector(const std::vector<int>& v, int n) {
    if (n == 0) return v[0];
    return v[n] + sumaVector(v, n - 1);
}

Nota:: La forma de invocar a la función en C++ podría ser: sumaVector(v, (int)v.size() - 1) (asumiendo v.size() > 0).

2) ¿Está ordenado de forma creciente? (recursivo)

P1 — C

#include <stdbool.h>

bool ordenado(int v[], int n) {
    bool res;

    if (n == 0) {
        res = true;
    } else {
        res = (v[n] >= v[n - 1]) &&
              ordenado(v, n - 1);
    }

    return res;
}

P2 — C++

#include <vector>

bool ordenado(const std::vector<int>& v, int n) {
    if (n == 0) return true;
    return (v[n] >= v[n - 1]) && ordenado(v, n - 1);
}

3) Contar dígitos impares de un número (recursivo)

P1 — C

int imparesNumero(int n) {
    int res;

    if (n == 0) {
        res = 0;
    } else {
        int ultimo = n % 10;

        if (ultimo % 2 != 0) {
            res = 1 + imparesNumero(n / 10);
        } else {
            res = imparesNumero(n / 10);
        }
    }

    return res;
}

P2 — C++

int imparesNumero(int n) {
    if (n == 0) return 0;
    int ultimo = n % 10;
    return (ultimo % 2 != 0) ? (1 + imparesNumero(n / 10))
                             : imparesNumero(n / 10);
}

Nota: si quieres que imparesNumero(0) cuente como “0 tiene 0 impares”, está bien tal cual.

4) Cadenas: contar vocales (recursivo con índice i)

P1 — C

#include <stdbool.h>

bool esVocal(char c) {
    return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||
           c=='A'||c=='E'||c=='I'||c=='O'||c=='U';
}

int contarVocales(char cad[], int i) {
    int res;

    if (cad[i] == '\0') {
        res = 0;
    }
    else if (esVocal(cad[i])) {
        res = 1 + contarVocales(cad, i+1);
    } else {
        res = contarVocales(cad, i+1);
    }
    return res;
}

P2 — C++

#include <string>

bool esVocal(char c) {
    return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||
           c=='A'||c=='E'||c=='I'||c=='O'||c=='U';
}

int contarVocales(const std::string& cad, std::size_t i) {
    if (i >= cad.size()) return 0;
    return esVocal(cad[i]) ? (1 + contarVocales(cad, i + 1))
                           : contarVocales(cad, i + 1);
}