Question

Prove that the recursive algorithm for finding the reversal of a bit string that you gave in Exercise 37 is correct.

Short answer

It has been proved that recursive algorithm is correct.

Step-by-step solution

Given that

Given the recursive algorithm for the reversal of bit string 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)

Prove the correctness of algorithm

The algorithm correctly gives the reversal of bit string $\lambda$.

Because $\lambda$ (the basis step of our proof by mathematical induction on n), and because the reversal of a string consists of its last character followed by the reversal of its first n - 1 characters, the algorithm behaves correctly when n > 0 by the inductive hypothesis.