Make it simple, THEN make it fast/efficient.

Here's a tail-recursive function. To be honest I would have started writing this version first, the acc pattern is ubiquitous. Sorry for the mistakes, I'm on mobile:

    def zip(a, b) do
      zip(a, b, [])
    end

    def zip([], _, acc), do: acc

    def zip(_, [], acc), do: acc

    def zip([a | a_rest], [b | b_rest], acc) do
      zip(a_rest, b_rest, [{a,b}|acc])
    end

Also, there's Enum.zip/2 in the standard library, with the bonus that it works with any Enumerable type (lists, maps, lazy streams, etc,)