Recursion continued

A friend of mine likes Palindromes, and was trying to figure out a way of seeing which sentences are Palindromes from a list of combinations of words. I don't exactly know how the combination maker works, but that part is recursive.

The part of his code that checks for a Palindrome is iterative, however. It checks the String from its beginning and its end, and makes comparisons based on those. If a letter pair doesn't match, it terminates. Otherwise it returns true.

It's pretty fast.

My recursive method, on the other hand, takes a String and splits it into two halves, and reverses the second half (so that ecar = race), and then does comparisons based on that.

It's pretty slow. But its also turning up an extra Palindrome or two every now and then. Which I think has to do with how its doing its calculations.

If I could somehow optimize my recursion to break if it knows its false i could probably speed it up greatly.

Which one's better? I don't know.

Also, for if tests, especially when calling a method in a return line, I think I found a pretty nifty way of indenting my code.

take

function foo (int num) {
     if (num == 0) {
          return 1;
     }
     else {
          return
               1
               + foo(num--);
     }
}

i think this is a lot better than

function bar(int num) {
     if (num == 0)
          return 1;
     else return 1 + bar(num--);
}

With the former, you can easily tell that it's returning a number and then calling itself. With the latter, you have to take in both as one step. This isn't so bad at first, but when you have something like

public String flip(String word) {
     if (word.length() ==1) {
          return 
               word.substring(word.length() - 1, word.length());
     }

     else {
          return 
               word.substring(word.length() - 1, word.length()) 
                    + flip(word.substring(0, word.length() - 1));
     }
}

Where the return statements get a little long winded, it can be quite nice to break them up into smaller pieces. Of course, all the indention can get a little long winded, but, indenting has always been a sign that you're going a little bit deeper into the logic of an operation (nested if tests, nested loops, etc)

Since recursion breaks down a problem into its subproblems, and then returns a combined result, I believe this way makes sense, too. When you break a problem into a smaller part, you're going further into the logic... When you're done, you're coming out.

Recursion is recursion is recursion is recursion is recursion . . .

So, bought a book the other day, called "Introduction to Algorithms", which is a heavy, thick book that covers well, algorithms in computing, makes a case for them as a technology (it is not enough to have fast hardware, the instruction set must be efficient, as well), and goes on and on with tons of heavy calculus that I don't well, understand all that well. So far I've read up on insertion sort and merge sort, and, while I actually did make (read: copy) an insertion sort algorithm and make it work (correctly), I never did a merge sort.

See, the problem with recursion is that, its not very easy to see where its going. Yet, for some problems, recursion is the way to go. Take the game Portal and its view of looking through portals like in a mirror (It's really something better shown than explained... but the next time you see two mirrors directly opposite each other, its like that). They explain in the commentary that this is done recursively. And it makes sense. I couldn't see how it'd be doing using iterations.

Except... recursion is a type of loop. But a special type of loop. One that is actually very elegant and beautiful. It is also not all that verbose, compared to that of say a for loop or while loop.
// sorry about the lack of indents. Blogger doesn't like lots of spaces for some reason
Consider . . . (in Java syntax, at least. Well, I think this is correct. Merge sort isn't working but this is from the book)

merge (A, p, r) {
     if p < r) {
          q = (p + r) / 2;
          merge (A, p, q);
          merge (A, q + 1, r);
          merge (A, p, q, r);
    }
}

where the method merge (A, p, r) calls itself several times, breaks its problem down through both halves of the array and then reassembles the list in sorted order, which is what the last method does. At least, this is how I understand it.

Merge sort I do not actually have working. I have something, and by something I mean it sort of sorts an array and loses a huge chunk of data by the time its done. And why I don't know.

This is a lot more elegant than, say, the insertion sort with its for loop and while loop, although a bit harder to grasp. Merge sort, however, is quite efficient for large arrays.

Where was I going with this? Well, I just built a word-counter program that solves counting words line by line recursively. It reads in a line, takes out the first word, and calls itself with the new sentence. It's exit condition is satisfied when the line it is working with no longer contains a space.

It isn't perfect by any means. A long trail of spaces, or, say, a blank line will up the word count per space or per line. Putting in the wrong file name will terminate the program without any explanation as to why. That I need to fix. Maybe I could throw some other checks in there to make sure that the line doesn't contain nothing or doesn't count extra spaces. I mean, maybe that would be easy. But it means more steps, too.

But then computers are fast, anyway. No, I mean, seriously fast.