3

Does every recursive function have an equivalent for loop? (Both achieve the same result).

I have this recursive function:

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    if(words[length].contains(word.substring(0, length)))
        return recur(word.substring(length), word.length() - length);
    return recur(word, length-1);
}

Given that words is a Set[], and where words[i] = a set with words of length i.

What am trying to do is: initiate the recursion with a word (say, "stackoverflow", no spaces), I am trying to find if this word can be cut into subwords ("stack", "over", "flow") .. minimum length of a subword is 3, and given that the subword of lenght i is in the Set words[i].

I can confirm this code works, but it may have a memory problem, so I want to turn it to a loop.. if possible.

Do you need more info??

Thanks.

Improve this question

5 Answers 5

Reset to default
6

Tail recursion can always be unrolled into a loop and your code is pretty close to tail recursion, so yes.

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    int nextLength;
    String nextWord;
    if(words[length].contains(word.substring(0, length))) {
      nextWord = word.substring(length);
      nextLength = word.length() - length;
    } else {
      nextWord = word;
      nextLength = length - 1;
    }
    return recur(nextWord, nextLength);
}

This is now proper tail recursion. Now to turn it into a loop:

private static boolean recur(String word, int length) {
    int nextLength = length;
    String nextWord = word;
    while( true ) {
        if(nextLength == 1 || nextLength == 2)
            return false;
        if(nextLength == 0)
            return true;
        if(words[nextLength].contains(nextWord.substring(0, nextLength))) {
            nextWord = nextWord.substring(nextLength);
            nextLength = nextWord.length() - nextLength;
        } else {
            nextWord = nextWord;
            nextLength = nextLength - 1;
        }
    }
}

Note that this code can be further optimised, I just wanted to demonstrate the "automatic" method of turning recursion into a loop.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

It's not only close to tail recursive. There are two recursive calls and both are the last thing that's done. Tail recursion does not mean that there is only a single recursive call which is the last line of the function (as in your "proper" example).
Well, the automatic is EXACTLY what I was looking for, for now at least, thanks. And TBH, I need it to solve a programming problem, so showing me how it can be optimized will help me avoid "time limit exceeded" errors ;)
@musiKk We learned a stricter definition of tail recursion at uni, but I checked it and you're right. The steps of conversion are still the same.
@Mazyod Jaleel See @Dave Hinton's answer. It's not so much optimisation as removing visual clutter, but still.
@biziclop : can you help me with this recursion - stackoverflow.com/questions/13229722/… . I think it is similar to this problem. I am not sure if you can call it a tail recursion. The recursion is at the end of each if statement.
5

For the general question: Yes every recursion can be transformed in a loop. You can model the the stack created and used by recursion explicitely and modify it in the loop.

For the specific problem:

Looking at your code as a function and ignoring side effects I think you could just return false.

If you actually need the split words try the following:

have a list with the word to split.
iterate until list after iteration is the same as before.
    iterate over list
        if the word can be split, replace it in the list with its parts
    end of loop
end of loop
Improve this answer

Comments

2

Short answer: in general you can, in this case you can easily, but if you fix the bug in your code's logic you have to worry about maintaining a stack yourself.

Long answer:

First, the iterative version of your recursive method:

private static boolean recur(String word, int length) {
    while(true) {
        if(length == 1 || length == 2)
            return false;
        if(length == 0)
            return true;
        if(words[length].contains(word.substring(0, length))) {
            int newlen = word.length() - length;
            word = word.substring(length);
            length = newlen;
        }
        else {
            --length;
        }
    }
}

This works by replacing the recursive call with assignment to the parameters, and sticking it all in a loop.

But like your original code, this contains a bug!

(I can't think of actual words that this bug works with, so imagine my made up words are real words.)

Suppose your long word is ABCDEFGH, and that ABCD, EFGH, and ABCDE are all words, but FGH isn't. recur looks for the longest word first, so it will match ABCDE, then discover that FGH isn't a word, and tell you that ABCDEFGH can't be cut into subwords.

But it could be split into ABCD and EFGH! It misses the shorter initial match because you don't consider other options once you've found a match. (And if your code started by looking for the shorter match, it still wouldn't work if ABC was a word and DEFGH wasn't.)

So:

private static boolean recur(String word, int length) {
    if(length == 1 || length == 2)
        return false;
    if(length == 0)
        return true;
    return (words[length].contains(word.substring(0, length)))
            && recur(word.substring(length), word.length() - length))
           || recur(word, length-1);
}

Now, turning this into an iterative method is harder: sometimes you have two recursive calls. That means simply assigning to your parameters won't work, because you need the parameters' original values to calculate the parameters for the second call. You have to explicitly manage a stack or a queue with all the different values, because now the language isn't doing it for you.

Improve this answer

4 Comments

In general, you can. All you have to do is think of the divide between recursive and non-recursive, as the divide between implicit or explicit stack.
I missed that special case for some reason, and you saved me the pain of finding it! but still, thats not the answer to the question.. so thanks, but i cant choose it as best answer..
@Martinho Very true --- I meant to point out that it was not as easy when the original function was not tail recursive, and in my haste wrote it wrong :-(
yes, it is easy to see why it is possible (you just need to think about the stack), but it's not that easy to see how it is possible unless it's tail recursion.
1

I answer your first question: Yes, every recursive function has an iterative equivalent. Read more.

This also is kind of related to CPS (not exactly because tail calls aren't really supported by popular Java VMs). Converting a tail recursive function (such as the one in the question) should be especially easy.

Improve this answer

Comments

0

@biziclop demonstrates how to refactor the code to be non recursive. I would go further and reduce the code so that.

  • The length is no longer passed as an argument.
  • Two loops are used to simplify the logic.
  • modify the local word value to simplify.

code

private static boolean recur(String word) {
    LOOP: for(;;) {
        for (int len = word.length(); len >= 3; len--)
            if (words[len].contains(word.substring(0, len))) {
                word = word.substring(len);
                continue LOOP;
            }
        return word.length() == 0;
    }
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.