Not. Just because a functional function is implemented with an imperative code behind the scenes, which does not make this function mandatory. Our computers are required; therefore, at some point, the entire functional code must be implemented by translating into imperative code!
The key value here is this: functional programming refers to the interface , not the implementation . A piece of code is functional if the code itself cannot observe any side effects, even if the side effects actually occur behind the scenes. If you check the value of the same binding of the same variable several times, you will get the same value, even if that value was put there behind the scenes with set! .
In the case of letrec , a little is caught here: the result is undefined if evaluating any of the bindings in letrec leads to the fact that the other can be replaced. So, the result of this code is undefined:
(letrec ((foo bar) (bar 7)) (cons foo bar))
The value of foo in the body of letrec is undefined. On the other hand, the result is as follows:
(letrec ((foo (lambda () bar)) (bar 7)) (cons (foo) bar))
This is because when evaluating lambda , the link is linked to the bar, but the actual value is not viewed until the closure is done in the body.