One consideration is whether your algorithm is intended to be an abstract solution, or a practical executable solution. In the former case, the attributes you are looking for are correctness, and ease of understanding for your target audience1. In the latter case, performance is also an issue. These considerations may influence your choice.
A second consideration (for a practical solution) is whether the programming language (or more strictly, its implementation) that you are using do tail-call elimination? Without tail-call elimination, recursion is slower than iteration, and deep recursion may lead to stack overflow problems.
Note that a (correct) recursive solution can be transformed into an equivalent non-recursive solution, so you don't necessarily need to make a hard choice between the two approaches.
Finally, sometimes the choice between recursive and non-recursive formulations is motivated by the need to prove (in the formal sense) properties about an algorithm. Recursive formulations more directly allow proof-by-induction.
1 - This includes considerations like whether the target audience ... and this might include programmers reading practical code ... would view one style of solution as "more natural" than the other. The notion of "natural" will from person to person, depending on how they learned programming / algorithmics. (I challenge anyone who proposes "naturalness" as the primary criteria for deciding to define "naturalness" in objective terms; i.e. how would you measure it.)