Having done pages and pages of long division by hand, I've been wondering weather it would be possible to in fact use a recursive function to achieve the same effect? The specific context of me using the algorithm is in searching for the greatest common divisor of two horribly long polynomials. Assuming the values of 'x' in the polynomials are in fact irrelevant, would this be possible through recursion?

Yes, it is possible.
Here is a detailed explanation:
http://mathworld.wolfram.com/EuclideanAlgorithm.html
As Mathworld says, this algorithm is applicable to any Euclidean ring, not just Z.
Note that C[ z ], the set of all complex polynomials, is a Euclidean ring, but R[ x ], the set of all real polynomials, isn't.
You will likely have to implement complex polynomial division to translate the algorithm into code.

Thanks that helps alot.
I'll probably wait till we cover recursion again before I try putting it into any code.