Are there algorithms or circuits that can implement addition without the need for carry flags

Let two numbers $x,y$ be represented in some digit form (binary, octal, ...): $(x_1 x_2 x_3 \ldots)$ and $(y_1 y_2 y_3 \ldots)$.

Can we add those numbers such that we do not need to carry over: $x_i = x_i+y_i + c(x_{i-1},y_{i-1})$ where $c(x_{i-1},y_{i-1})$ is the carry value of $x_{i-1}$ and $y_{i-1}$.

Are there $O(1)$ step circuit implementations of addition that exist? Are they practical?

In other words, is addition inherently recursive over the number of digits?

For non-redundant representations like $(x_n, x_{n-1}, ..., {x_1})$ the recursion is fundamental (although the operator is associative so you can apply the prefix sum optimization to parallelize the operation down to $O(\lg n)$ steps.)

But there are redundant representations where addition can be performed more efficiently, in some cases. The carry-save adder is used in most hardware multiplier implementations, where you need to sum together a large list of numbers.

The redundant representation is just to represent every number by two subsums:

c3 c2 c1
x3 x2 x1 x0

so, for example, the number "5" can be stored either as:

0  0  0
 0  1  0  1

or

0  0  1
 0  0  1  1

The "addition" operation adds three subsums and produces two subsums:

0  0  1
+0  0  1  1
+0  0  0  1
-----------
 0  1  1  0
 0  0  0  0

So, not very useful if you are just adding two numbers, but when you need to sum a whole list of numbers, each individual addition is fast, and then only at the end do you have to convert back to a non-redundant representation.

There are other redundant representations used in hardware multiplication algorithms, like Booth encoding where the digits can be positive, zero or negative.

StackExchange Computer Science Q#24653, answer score: 5