Question

Give a recursive algorithm for finding the reversal of a bit string. (See the definition of a bit string in the preamble of Exercise 34 in Section 5.3.).

Short answer

The recursive algorithm for reversal of a bit string is given.

Step-by-step solution

Given that

As per Question 34 in Section 5.3

The recursive definition of the reversal of a string is such that

$(vy{)}^R=y\left(v^R\right)$, where yis the last symbol in the string and vis the substring consisting of all but the last symbol.

The right-hand side of the last statement in this procedure means concatenate $b_n$with the output of the recursive call.

Write recursive algorithm

The recursive algorithm is as:

procedure reverse(b₁b₂…b_n: bit string)

if n = 0 then return$\lambda$

else return b_n reverse(b₁b₂…b_n-1)