Can a recursive function have iterations/loops?

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?

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.

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.

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)
        {
            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;
}

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.

Filed under: softwareengineering - @ 22:22

Thẻ: java, recursion

Thiết kế website giá rẻ

Danh mục

Can a recursive function have iterations/loops?