Под эквивалентностью я подразумеваю равенство выходных данных и произведенных побочных эффектов
Например, для двух функций вычислений n-го числа фибоначчи (питон)
def fib1(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def fib2(n):
if n < 2:
return n
return fib2(n-1) + fib2(n-2)
Питон тут для примера, для какого-нибудь лиспа, наверное, проще будет сделать это
