> Try writing fibonacci with everything immutable in say something simple like JS or python. Good luck doing it without using recursion or reduce.

SSA, no recursion, no reduce ;)

    def factorial(X: int) -> int:
        encode = lambda n: ((lambda N: lambda g: lambda f: lambda x: x if N == 0 else f(g(N-1)(g)(f)(x)))(n)
                            (lambda N: lambda g: lambda f: lambda x: x if N == 0 else f(g(N-1)(g)(f)(x))))
        decode = lambda f: f(lambda x: x + 1)(0)
        fact = (lambda f: lambda n: cond(vaut0(n))(lambda _: un)(lambda _: mult(n)(f(f)(pred(n)))))(
               (lambda f: lambda n: cond(vaut0(n))(lambda _: un)(lambda _: mult(n)(f(f)(pred(n))))))(n)
        return decode(fact(encode(X)))

Of course, I'm joking, as the Y combinator is clearly visible here.

Full form for those interested : https://termbin.com/cd3q