How to come up with the gamma function?

Here is a nice paper of Detlef Gronau Why is the gamma function so as it is?.
Concerning alternative possible definitions see Is the Gamma function mis-defined? providing another resume of the story Interpolating the natural factorial n! .

Concerning Euler's work Ed Sandifer's articles 'How Euler did it' are of value too, in this case 'Gamma the function'.

I guess you can say this is yet another application of the power of integration by parts (and I am guessing that is how the integral formula "was come up with" initially).

If you are trying to find the antiderivative of $P(t) e^t$, where $P(t)$ is a polynomial, integration by parts arises naturally and I would say it(integral of $P(t) e^t$) is quite natural to encounter during ones study of mathematics. And if you actually work it out, you notice the factorial like recursion. We can rid of the "non-integral" parts of the integration by parts formula by using the limits $0$ and $\infty$.

If $I_n = \int_{0}^{\infty} t^n e^{-t} \text{dt}$ then integration by parts gives us

$$I_n = -e^{-t}t^n|_0^{\infty} + n\int_{0}^{\infty} t^{n-1} e^{-t} = nI_{n-1}$$

so if

$f(x) = \int_{0}^{\infty} t^x e^{-t} \text{dt}, \quad x \ge 0$

then

$f(x) = x f(x-1), \quad x \ge 1$.

Also, we have that $f(0) = 1$, thus the integral definition agrees with the factorial function at the non-negative integers and can serve as a real extension for factorial.

Using Analytic continuation its domain can be extended further.

$$ \int e^{ax} dx = \frac{1}{a} e^{ax} + c $$

Take $\left .\frac{d}{da}\right |_{a=1}$ on both sides $n$ times, and algebra to get rid of $(-1)^n$, you'll have an integral equal to $n!$.

This is an intuitive way to get the Gamma function. You've shown that for integers it holds from this simple derivation.

Mathematicians then went through a great deal of work to show that it holds true for allot more than just the integer case.