Recursividad

def factorial(n):
    if n <= 1:
        return 1                                # caso base: se resuelve sin llamarse
    return n * factorial(n - 1)                 # caso recursivo: un problema más pequeño


def suma_digitos(n):
    if n < 10:
        return n                                # un solo dígito
    return n % 10 + suma_digitos(n // 10)       # el último + la suma de los demás


def potencia(base, exp):
    if exp == 0:
        return 1
    return base * potencia(base, exp - 1)


def invertir(s):
    if len(s) <= 1:
        return s
    return invertir(s[1:]) + s[0]               # el resto invertido + el primero al final


print("5! =", factorial(5))
print("Suma de los dígitos de 4096 =", suma_digitos(4096))
print("2^10 =", potencia(2, 10))
print("«recursividad» al revés:", invertir("recursividad"))

function factorial(n) {
    if (n <= 1) return 1;                       // caso base: se resuelve sin llamarse
    return n * factorial(n - 1);                // caso recursivo: un problema más pequeño
}

function sumaDigitos(n) {
    if (n < 10) return n;                       // un solo dígito
    return (n % 10) + sumaDigitos(Math.floor(n / 10));   // el último + la suma de los demás
}

function potencia(base, exp) {
    if (exp === 0) return 1;
    return base * potencia(base, exp - 1);
}

function invertir(s) {
    if (s.length <= 1) return s;
    return invertir(s.slice(1)) + s[0];         // el resto invertido + el primero al final
}

console.log("5! = " + factorial(5));
console.log("Suma de los dígitos de 4096 = " + sumaDigitos(4096));
console.log("2^10 = " + potencia(2, 10));
console.log("«recursividad» al revés: " + invertir("recursividad"));

using System;

class Program {
    static long Factorial(int n) {
        if (n <= 1) return 1;                      // caso base: se resuelve sin llamarse
        return n * Factorial(n - 1);               // caso recursivo: un problema más pequeño
    }

    static int SumaDigitos(int n) {
        if (n < 10) return n;                      // un solo dígito
        return n % 10 + SumaDigitos(n / 10);       // el último + la suma de los demás
    }

    static long Potencia(long b, int exp) {
        if (exp == 0) return 1;
        return b * Potencia(b, exp - 1);
    }

    static string Invertir(string s) {
        if (s.Length <= 1) return s;
        return Invertir(s[1..]) + s[0];            // el resto invertido + el primero al final
    }

    static void Main() {
        Console.WriteLine("5! = " + Factorial(5));
        Console.WriteLine("Suma de los dígitos de 4096 = " + SumaDigitos(4096));
        Console.WriteLine("2^10 = " + Potencia(2, 10));
        Console.WriteLine("«recursividad» al revés: " + Invertir("recursividad"));
    }
}

<?php
function factorial(int $n): int {
    if ($n <= 1) return 1;                     // caso base: se resuelve sin llamarse
    return $n * factorial($n - 1);             // caso recursivo: un problema más pequeño
}

function sumaDigitos(int $n): int {
    if ($n < 10) return $n;                    // un solo dígito
    return $n % 10 + sumaDigitos(intdiv($n, 10));   // el último + la suma de los demás
}

function potencia(int $base, int $exp): int {
    if ($exp === 0) return 1;
    return $base * potencia($base, $exp - 1);
}

function invertir(string $s): string {
    if (strlen($s) <= 1) return $s;
    return invertir(substr($s, 1)) . $s[0];    // el resto invertido + el primero al final
}

echo "5! = " . factorial(5) . "\n";
echo "Suma de los dígitos de 4096 = " . sumaDigitos(4096) . "\n";
echo "2^10 = " . potencia(2, 10) . "\n";
echo "«recursividad» al revés: " . invertir("recursividad") . "\n";

llamadas = 0


def fib(n):                                     # ingenuo: recalcula lo mismo una y otra vez
    global llamadas
    llamadas += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)


memo = {}


def fib_memo(n):                                # con memoización: cada fib(k) se calcula una vez
    global llamadas
    llamadas += 1
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]


llamadas = 0
a = fib(25)
print(f"fib(25) = {a} con {llamadas} llamadas")
llamadas = 0
b = fib_memo(25)
print(f"fibMemo(25) = {b} con {llamadas} llamadas")

let llamadas = 0;

function fib(n) {                               // ingenuo: recalcula lo mismo una y otra vez
    llamadas++;
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

const memo = new Map();

function fibMemo(n) {                           // con memoización: cada fib(k) se calcula una vez
    llamadas++;
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const r = fibMemo(n - 1) + fibMemo(n - 2);
    memo.set(n, r);
    return r;
}

llamadas = 0;
const a = fib(25);
console.log(`fib(25) = ${a} con ${llamadas} llamadas`);
llamadas = 0;
const b = fibMemo(25);
console.log(`fibMemo(25) = ${b} con ${llamadas} llamadas`);

using System;
using System.Collections.Generic;

class Program {
    static long llamadas = 0;

    static long Fib(int n) {                       // ingenuo: recalcula lo mismo una y otra vez
        llamadas++;
        if (n <= 1) return n;
        return Fib(n - 1) + Fib(n - 2);
    }

    static readonly Dictionary<int, long> memo = new();

    static long FibMemo(int n) {                   // con memoización: cada fib(k) se calcula una vez
        llamadas++;
        if (n <= 1) return n;
        if (memo.TryGetValue(n, out long guardado)) return guardado;
        long r = FibMemo(n - 1) + FibMemo(n - 2);
        memo[n] = r;
        return r;
    }

    static void Main() {
        llamadas = 0;
        long a = Fib(25);
        Console.WriteLine(
quot;fib(25) = {a} con {llamadas} llamadas");
        llamadas = 0;
        long b = FibMemo(25);
        Console.WriteLine(
quot;fibMemo(25) = {b} con {llamadas} llamadas");
    }
}

<?php
$llamadas = 0;

function fib(int $n): int {                    // ingenuo: recalcula lo mismo una y otra vez
    global $llamadas;
    $llamadas++;
    if ($n <= 1) return $n;
    return fib($n - 1) + fib($n - 2);
}

$memo = [];

function fibMemo(int $n): int {                // con memoización: cada fib(k) se calcula una vez
    global $llamadas, $memo;
    $llamadas++;
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fibMemo($n - 1) + fibMemo($n - 2);
}

$llamadas = 0;
$a = fib(25);
echo "fib(25) = $a con $llamadas llamadas\n";
$llamadas = 0;
$b = fibMemo(25);
echo "fibMemo(25) = $b con $llamadas llamadas\n";