Enquanto isso, na programação funcional...

Na programação funcional não existem valores parciais, então não dá para fazer o mesmo truque. Também seria estranho ver procedimentos em uma linguagem funcional. Mas ainda dá para conseguir recursividade final (já vi em algum lugar a tradução recursão de cauda ou algo similarmente horrendo) através de outra transformação. A idéia é utilizar uma convenção idiomática comum, através de acumuladores. Vejamos como isso fica em Scheme. A função mapl (map já existe em Scheme) é uma versão direta da função em Oz:

(define (mapl f l)

(if (null? l)

   ()

   (cons (f (car l)) (mapl f (cdr l)))))

Ela claramente não apresenta recursividade final. Agora vamos passar utilizar um acumulador como parâmetro adicional:

(define (mapla f l a)

(if (null? l)

    a

    (mapla f (cdr l)

           (cons (f (car l)) a))))

E voilà: tail recursion. Mas aqui temos um problema: a lista resultante está invertida com relação ao resultado esperado, pois a operação de construção de lista não é comutativa. Resolve-se isso adicionando uma chamada a reverse:

(define (mapla f l a)

(if (null? l)

    (reverse a)

    (mapla f (cdr l)

           (cons (f (car l)) a))))

Pode testar que dá o mesmo resultado (recomendo o DrScheme); como acumulador inicial usa-se a lista vazia, segundo a equação de equivalência (mapl f l) = (mapla f l ()). Pode-se criar uma função wrapper que faça isso automaticamente.