elementwise combination of two lists in R

expand.grid(list.a, list.b) gives you the desired result in a data.frame. This tends to be the most useful format for working with data in R. However, you could get the exact structure you ask for (save the ordering) with a call to apply and lapply:

result.df <- expand.grid(list.a, list.b)
result.list <- lapply(apply(result.df, 1, identity), unlist)

If you want this list ordered by the first element:

result.list <- result.list[order(sapply(result.list, head, 1))]

You want mapply (if by "recursively" you mean "in parallel"):

mapply(c, list.a, list.b, SIMPLIFY=FALSE)

Or maybe this is more what you want:

unlist(lapply(list.a, function(a) lapply(list.b, function (b) c(a, b))), recursive=FALSE)