Calculating N-th step of recurrent sequence

another way:

NestList[N[1/2 (# + a/#) &], 1, 5] /. a -> 16
{1, 8.5, 5.19118, 4.13666, 4.00226, 4.}

Here's one direct way to define the recursion:

Clear[f];
f[n_, a_] := f[n, a] = 1/2 (f[n - 1, a] + a/f[n - 1, a]);
f[0, a_] := 1;

For example, f[10,1] gives 1 and

f[10, 2] // N

1.41421

which is probably pretty close to Sqrt[2].

You can use RSolve whith the boundary condition x0

x0 = 1;
f[N_, A_, x0_] := Re[RSolve[{x[n + 1] == 1/2 (x[n] + a/x[n]), x[0] == x0},
                            x[n],  n][[1, 1, 2]] /. {n -> N, a -> A}]
f[10, 2., x0]