How do you solve this recurrence? I have been trying to practice recurrence relations that can be solved by the master theorem and came across this.

Now the $4^{\textrm{th}}$ problem in that file is :

$$T(n) = 2^n T\left(\frac{n}{2}\right) + n^n.$$

The solution says it can't be solved using Master theorem, which is true. But I want to know how to solve it.

I tried thinking of some substitution but I'm not able to get anywhere since the recurrence contains terms $2^n$ and $n^n$ both. And if I expand the tree, it becomes really messy. Any solutions?
Introducing $U(n)=T(n)/4^n$, one sees that $U(n/2)=T(n/2)/2^n$ hence the recursion over $(T(n))_n$ yields $U(n)=U(n/2)+(n/4)^n$.

Roughly speaking, this means that $U(n)=(n/4)^n+(n/8)^{n/2}+(n/16)^{n/4}+\ldots$ More rigorously, the $\ldots$ hides at most $\log_2n$ terms, each less than $(n/8)^{n/2}$, hence 
$$
(n/4)^n\leqslant U(n)\leqslant(n/4)^n+\log_2(n)\cdot(n/8)^{n/2},
$$
which implies
$$
n^n\leqslant T(n)\leqslant n^n+\log_2(n)\cdot(2n)^{n/2}.
$$
Since $\log_2(n)\cdot(2n)^{n/2}\ll n^n$, this yields $\lim\limits_{n\to\infty}T(n)/n^n=1$, hence $T(n)=\Theta(n^n)$.
Hint: if  $k = T(n)/n^n$ then $$T(2n) = k 2^{2n}n^n +(2n)^{2n} = \left(k/n^n+1\right) (2n)^{2n}$$