There is an informal concept of "function", which says that a function is any correspondence (itself an informal term) that assigns one definite output value to each input value of the function.
This informal concept has various formalizations, depending on the precise use one has for it.
The set-based concept of a function as a set of ordered pairs such that there is nothing that is the first element of two different pairs in the set. Such a function has a set as its domain and a set of its range, and it is a subset of the Cartesian product of the domain and the range.
Here, in particular, it doesn't matter where we get the set from, as long as it satisfies the defining condition. In particular, the set-theoretic Axiom of Choice states that there exist function with particular properties without giving any kind of "rule" for how to find the output for a particular input.
The set-based formalization is be convenient and expressive enough that it is the default choice for formalizing functions in many areas of mathematics, together with the general tendency to formalize everything in set theory. But it is not the only one possible, and in some situations a different formalization is more useful:
In logic and related areas is is common to model a function simply as a symbol together with axioms and equations that state properties that we want the symbol to have. For example, the Peano Arithmetic axioms for the natural numbers posit that there is a successor function and addition/multiplication functions that are not considered objects in themselves but simply symbols that can be manipulated according to certain rules. Intuitively, these symbols are to be thought of as realizing the informal concept of a function.
This is not as expressive as the usual set-based concept, but is convenient because it can be used in settings where one wishes to avoid depending on set theory for one reason or another.
In higher-order logic, one can even quantify over this kind of functions.
Also in logic, sometimes a "function" is considered to be simply a logical formula with two variables, $\varphi(x,y)$ such that $\forall x,y,z:\varphi(x,y)\land \varphi(x,z)\to y=z$ is true (or provable, depending on your needs).
In some ways, this is stronger than the usual formalization, which is necessary for some purposes within set theory itself -- for example, the successor function for ordinal numbers can be expressed as a formula but is not a set in standard set theory. On the other hand, if we allow additional parameters in $\varphi$ we can express every set function, because $(x,y)\in f$ is a good formula when $f$ is a set that represents a function in the ordinary way.
On the other other hand, viewing functions as formulas means that one cannot quantify over functions (that is, one cannot say that such-and-such holds for all functions of a certain kind, nor that there is some function with such-and-such property).
In lambda calculus, used in computer science and related areas, the basic kind of object is a function, represented as an actual expression for how to compute function values, wrapped up as a mathematical object in its own right.
This view is useful for reasoning about computable functions rather than the unlimited "wild" functions that the set-theoretic view lets us speak about. Being less expressive allows this formalization to allow more convenient reasoning of certain kinds.
The problem with saying that a function is just a "rule" is that the term "rule" itself needs a definite meaning before that concept says any more than the informal "correspondence" definition. For example, if we say
$f(n)$ is the length in words of the shortest English phrase that describes $n$ unambigously.
is that then a "rule"? If it is, then fairly soon we're hit by Berry's paradox. But if it is not, then the question of what exactly a valid "rule" is, demands to be answered. One may propose various answers, of course, but by their nature such an answer will lead to a concept of function that is something more than just saying "a rule".
