Exactly how I tried and it throws 'maximum recursion depth exceeded in comparison'. I thought I impoved it with memoizaition, but nope. Where did I go wrong?

Recursion can be fast enough if you cache the results.

Recursion isn't blocked. It's just for n > 25, a recursive fibonacci algorithm becomes quite slow.

Recursion is simply not suitable for some problems because it's limited by their size. Recursion uses call stack, and memory assigned for a it is usually not very large and the stack cannot grow indefinitely, that's why large problems can overflow it.
If you really want to use recursion, sometimes you need to redesign it in some way. "Simulate" it with an explicit, in-memory stack, take advantage of tail recursion (if possible), etc.

It's not a problem with the kata, its a flaw of the naive recursive approach.

Having the same issue in javascript here

The kata doesn't forbid recursion.

Recursion should be allowed in these katas. Simple memoized example below

def perimeter(n):
    memo = [1, 1]
    fib(n, memo)
    return 4 * sum(memo)

def fib(n, memo=[1, 1]):
    if len(memo) > n:
        return memo[n]
    memo.append(fib(n-1, memo) + fib(n-2, memo))
    return memo[-1]

I was a little annoyed with how easily this could be solved with recursion, but when you used recursion you run into an overflow error. This isn't the first problem that I've seen do this, but I think it limits the possible number of solutions.

Maybe it's a Python thing?