I've been studying about recursive functions, and apparently, they're functions that call themselves, and don't use iterations/loops (otherwise it wouldn't be a recursive function).

However, while surfing the web for examples (the 8-queens-recursive problem), I found this function:

private boolean placeQueen(int rows, int queens, int n) {
    boolean result = false;
    if (row < n) {
        while ((queens[row] < n - 1) && !result) {
            if (verify(row,queens,n)) {
                ok = placeQueen(row + 1,queens,n);
        if (!result) {
            queens[row] = -1;
        result = true;
    return result;

There is a while loop involved.

... so I'm a bit lost now. Can I use loops or not?

  • 9
    The entire definition of recursion is that at some point, the function may be re-called as part of its own execution before it returns (whether it's re-called by itself or by some other function it calls). Nothing about that definition excludes the possibility of looping.
    – cHao
    Commented Oct 26, 2012 at 22:29
  • As an addendum to cHao's comment, a recursive function will be re-call on an easier version of itself (otherwise, it would loop forever). To quote orbling (from In plain English, what is recursion?): "Recursive programming is the process of progressively reducing a problem in to easier to solve versions of itself." In this case, the hardest version of placeQueen is "place 8 queens" and the easier version of placeQueen is "place 7 queens" (then place 6, etc.)
    – Brian
    Commented Oct 27, 2012 at 0:26
  • You can use anything that works Omega. Very rarely do software specifications specify what style of programming to use --unless you are in school and your assignment says so.
    – Apoorv
    Commented Oct 27, 2012 at 2:08

8 Answers 8


You misunderstood recursion: although it can be used to replace iteration, there is absolutely no requirement for the recursive function not to have iterations internal to itself.

The only requirement for a function to be considered recursive is the existence of a code path through which it calls itself, directly or indirectly. All correct recursive functions also have a conditional of some sort, preventing them from "recursing down" forever.

Your recursive function is ideal to illustrate the structure of recursive search with backtracking. It starts with the check of the exit condition row < n, and proceeds to making search decisions on its level of recursion (i.e. picking a possible position for queen number row). After each iteration, a recursive call is made to build upon the configuration that the function has found so far; eventually, it "bottoms out" when row reaches n in the recursive call that is n levels deep.

  • 1
    +1 for "correct" recursive functions have a conditional, plenty of incorrect ones out there which don't heh Commented Oct 26, 2012 at 21:10
  • 7
    +1 "recurring down" forever `Turtle() { Turtle();}
    – Mr.Mindor
    Commented Oct 27, 2012 at 3:11
  • 1
    @Mr.Mindor I love the "It's turtles all the way down" quote :) Commented Oct 27, 2012 at 3:14
  • That made me smile :-) Commented Oct 27, 2012 at 11:17
  • 2
    "All correct recursive functions also have a conditional of some sort, preventing them from "recursing down" forever." is not true with non-strict evaluation.
    – Pubby
    Commented Oct 27, 2012 at 21:08

The general structure of a recursive function is something like this:

   if evaluateBaseCaseCondition(inputValue)=true then
       return baseCaseValue;
       Recursive processing
       recursiveResult = myRecursiveFunction(nextRecursiveValue); //nextRecursiveValue could be as simple as inputValue-1
       return recursiveResult;
   end if

The text that I marked as /*recursive processing*/ could be anything. It could include a loop, if the problem being solved requires it, and could also include recursive calls to myRecursiveFunction.

  • 1
    That's misleading, because it implies that there is only one recursive call, and pretty much excludes cases where the recursive call is itself inside a loop (e.g. B-tree traversal). Commented Oct 26, 2012 at 19:53
  • @PeterTaylor: Yes, I was trying to keep it simple. Commented Oct 26, 2012 at 20:12
  • Or even multiple calls without a loop, like traversing a plain binary tree, where you'd have 2 calls due to each node having 2 children.
    – Izkata
    Commented Oct 26, 2012 at 20:15

You surely can use loops in a recursive function. What makes a function recursive is only the fact that the function calls itself at some point in its execution path. However you should have some condition to prevent infinite recursion calls from which your function can't return.


Recursive calls and loops are just two ways / constructs to implement an iterative computation.

A while loop corresponds to a tail-recursive call (see e.g. here), i.e. an iteration in which you do not need to save intermediate results between two iterations (all the results of one cycle are ready when you enter the next cycle). If you need to store intermediate results that you can use again later you can either use a while loop together with a stack (see here), or a non tail-recursive (i.e. arbitrary) recursive call.

Many languages allow you to use both mechanisms and you can choose the one that better suits you and even mix them together in your code. In imperative languages like C, C++, Java, etc. you normally use a while or for loop when you do not need a stack, and you use recursive calls when you need a stack (you implicitly use the run-time stack). Haskell (a functional language) does not offer an iteration control structure so you can only use recursive calls to perform iteration.

In your example (see my comments):

// queens should have type int [] , not int.
private boolean placeQueen(int row, int [] queens, int n)
    boolean result = false;
    if (row < n)
        // Iterate with queens[row] = 1 to n - 1.
        // After each iteration, you either have a result
        // in queens, or you have to try the next column for
        // the current row: no intermediate result.
        while ((queens[row] < n - 1) && !result)
            if (verify(row,queens,n))
                // I think you have 'result' here, not 'ok'.
                // This is another loop (iterate on row).
                // The loop is implemented as a recursive call
                // and the previous values of row are stored on
                // the stack so that we can resume with the previous
                // value if the current attempt finds no solution.
                result = placeQueen(row + 1,queens,n);
        if (!result) {
            queens[row] = -1;
        result = true;
    return result;

You are right to think there is a relationship between recursion and iteration or looping. Recursive algorithms are often manually or even automatically converted to iterative solutions using tail call optimization.

In eight queens, the recursive part is related to storing data needed for back tracking. When you think of recursion, it is valuable to think about what is pushed on the stack. The stack can contain pass by value parameters and local variables that play a key role in the algorithm, or sometimes stuff that is not so apparently relevant like the return address or in this case, a passed value with the number of queens that is used but not changed by the algorithm.

The action that happens in eight queens is that essentially we are given a partial solution for some number of queens in the first few columns from which we iteratively determine valid-so-far choices in the current column that we pass recursively to be evaluated for the remaining columns. Locally, eight queens keeps track of what row it is trying and if the back tracking occurs, it is ready to step through the remaining rows or to back track further by simply returning if it finds no other row that could work.


The "create an smaller version of the problem" part can have loops. As long as the method calls itself passing as a parameter the smaller version of the problem, the method is recursive. Of course an exit condition, when the smallest possible version of the problem is solved and the method returns a value, must be provided to avoid an stack overflow condition.

The method in your question is recursive.


The one recursive function that you are likely to use most is the quicksort function. To sort an array, you partition the items into one half with the smaller values and one half with the larger values, then sort one half recursively, then sort the other half recursively.

However, in practice everyone implements it is a loop:

While range is large
    Partition into smaller and larger values
    Sort smaller subrange recursively 
    Replace range with larger subrange
End of while loop
Sort small range directly. 

So you have a function with a loop and recursion.


Recursion basically calls your function again and main advantage of recursion is saves memory. Recursion can have loops in it they are used to perform some other operation.

  • 1
    Beg to differ. Many algorithms can be recursive or iterative and the recursive solution is often much more memory intensive if you count return addresses, parameters, and local variables that must be pushed on the stack. Some languages detect and help optimize for tail recursion or tail call optimization, but this is sometimes language or code specific. Commented Oct 27, 2012 at 5:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.