Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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) {
            queens[row]++;
            if (verify(row,queens,n)) {
                ok = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

There is a while loop involved.

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

share|improve this question
3  
Does it compile. Yes. So why ask? –  Thomas Eding Oct 26 '12 at 21:33
5  
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 Oct 26 '12 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 Oct 27 '12 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. –  Monster Truck Oct 27 '12 at 2:08
    
@ThomasEding: Yes, of course it compiles and works. But I'm just studying engineering at the moment - What matters for me, at this point, is the strict concept/definition and not the way programmers employ it nowadays. So I'm asking if the concept I have is correct (which is not, it seems). –  Omega Oct 27 '12 at 16:13
add comment

7 Answers

up vote 33 down vote accepted

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.

share|improve this answer
    
+1 for "correct" recursive functions have a conditional, plenty of incorrect ones out there which don't heh –  Jimmy Hoffa Oct 26 '12 at 21:10
4  
+1 "recurring down" forever `Turtle() { Turtle();} –  Mr.Mindor Oct 27 '12 at 3:11
    
@Mr.Mindor I love the "It's turtles all the way down" quote :) –  dasblinkenlight Oct 27 '12 at 3:14
    
That made me smile :-) –  Martijn Verburg Oct 27 '12 at 11:17
1  
"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 Oct 27 '12 at 21:08
add comment

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

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

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.

share|improve this answer
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). –  Peter Taylor Oct 26 '12 at 19:53
    
@PeterTaylor: Yes, I was trying to keep it simple. –  FrustratedWithFormsDesigner Oct 26 '12 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 Oct 26 '12 at 20:15
add comment

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.

share|improve this answer
add comment

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)
        {
            queens[row]++;
            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;
        }
    }else{
        result = true;
    }
    return result;
}
share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  DeveloperDon Oct 27 '12 at 5:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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