function x = HadSolve(b)
% b is a columnn-vector and n is a power of 2.
% Solves the nxn Hadamard system Hn*x = b
n = length(b);
if n==1
x = b;
else
m = n/2;
% Wn*x = b looks like
% [ Hm Hm;Hm -Hm][x(1:m);x(m+1:n)] = [b(1:m);b(m+1:n)]
% so
% Hm*(x(1:m)+x(m+1)) = b(1:m)
% Hm*(x(1:m)-x(m+1)) = b(m+1:n)
% Working with these two equations we conclude that
% Hm*x(1:m) = (b(1:m)+b(m+1:n))/2
% Hm*x(m+1:n) = (b(1:m)-b(m+1:n))/2

x = [ HadSolve((b(1:m)+b(m+1:n))/2);...
HadSolve((b(1:m)-b(m+1:n))/2) ];
end

% Grading (3 points):
% 1 point: incorrect result but correct idea, or
% correct but very inefficient solution
% 2 points: correct but failed to handle n=1 case
% correct but 4 recursive calls instead of 2
% 3 points: correct
%
% common issues that I did not take off for:
% -lack of comments
% -having 2 base cases