It has been claimed that Pirahã, a Brazilian native language spoken in the Amazon region, is non-recursive, disallowing syntactic self-embedding altogether (Everett, 2005). This thesis investigates this claim. First, a formal definition of recursion is necessary, and we examine how this term appeared within mathematics and logic and how it made its way to formal linguistics. Our conclusion is that within Generative Grammar, recursion is to be understood as a finite set of functions that calls for itself, taking its previous output as its input (i.e. the operation Merge). It is responsible for the combinatorial nature of Grammar, a universal cognitive capacity, which confers I-language with its core property: discrete infinity. The unavailability of self-embedding in a given language is not evidence against the universality of recursion. Self-embedding representations are one, but only one of the possible external outcomes of the recursive computations within I-language. The second goal of this thesis is to present new fieldwork data on possessive DPs in Pirahã, showing that self-embedding in this structural domain is possible and productive. Putting it all together, our conclusion is that Everett s claim about the universality of recursion is both theoretically and empirically incorrect. The contribution of this thesis to the field of formal linguistics is twofold: it offers a better understanding of computability within I-language, and a new empirical-based assessment of syntactic embedding in Pirahã.