# 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?

• Does it compile. Yes. So why ask? Oct 26, 2012 at 21:33
• 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, 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.) 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. Oct 27, 2012 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). Oct 27, 2012 at 16:13

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

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`.

• 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). Oct 26, 2012 at 19:53
• @PeterTaylor: Yes, I was trying to keep it simple. 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. 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.

``````// 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.

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.

• 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. Oct 27, 2012 at 5:40