A declarative method in java for Palindrome Check

A declarative method is one with no assignment statement in the body of the method. Let us look at the two methods in the class below.

public class PalindromeCheck {
public static boolean check(String s){
if (s.length() == 0 || s.length() == 1) return true;
if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
return check(s.substring(1, s.length() - 1));
}

public static boolean icheck(String s){
while (s.length() != 0){
if (s.length() == 1) return true;
if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
s = s.substring(1, s.length() - 1);
}
return true;
}

         public static void main(String[] args) {
System.out.println(check("malayalam"));
System.out.println(check("maam"));
System.out.println(icheck("malayalam"));
System.out.println(icheck("maam"));
}
}

check method is declarative. It follows the classical strategy of  problem solving in mathematics. Given that a related problem can be solved, specify the relationship between the result of that problem and the original problem. The original string s is a palindrome if s.substring(1,s.length() - 1) is a palindrome and the first and last characters of s coincide. This is ensured by the order of the statements above. The first statement takes care of the base cases of recursion and termination is assured.

icheck is not complicated either.  It breaks the first logical disjunction into two and introduces the negation of one to control the while loop. The obligatory assignment statement to modify the string has to be introduced.

Why all this extra stuff  and for what purpose?
Is not Check  preferable because it is shorter and direct?

Recursion Is A Win Iteration A Low-level Implementation Artifact (RIAWIALIA)

"If in its continual development mathematics seldom if ever attains
a finality, the constant growth does mature some residue
that persists. But it is idle to pretend that what was good
enough for our fathers in mathematics is good enough for us,
or to insist that what satisfies our generation must satisfy the
next."
                                                                                                                                                                                                   Eric Temple Bell
                                                             "The Development of Mathematics"
                                                                       McGraw-Hill Book Company
                                                                   New York London 1945, p.172

My generation whether satisfied or not, had only FORTRAN to program digital computers. And it took away the natural mathematical thinking based on equivalences and implications. Equal to sign ('=') is used to change the bit pattern stored in memory. A DO loop is necessary to calculate a recursive function like factorial. Recursion is forbidden because it can not be efficiently implemented. FORTRAN simply did not allow recursion until 90's.

In the late 80's I found PROLOG, a language with no assignment statement and no iteration. Recursion is the norm to get any work done. That indeed is programming in logic far from formula translation into assignments and loops.

It is known in computing circles that recursion is expressive, elegant and conducive to increase in programmer productivity.

Jon Bentley  in his 1982 book "Writing Efficient Programs" informs us that

"Recursive procedures(that is, procedures that can call themselves) are powerful expressive tools that can greatly ease the design and implementation of a correct program. That lesson was made clear to me when I translated a nineteen-step iterative algorithm that I had written (which resulted in over 100 lines of code and took two twelve-hour days to debug) into a four-step recursive algorithm (which took less than 30 lines of code and took less than an hour to implement). Unfortunately, this expressive power is not without cost, because many implementations of recursion are slow."

Wow! 20 times increase in  productivity. Definitely Recursion is a win.

No wonder PROLOG programmers pity FORTRAN foot soldiers.

Jon Bentley in 1998 after some experimentation with C compilers:

"These little experiments have illustrated some big truths about recursion.

• Recursion is expressive. Some of the recursive tree functions are much clearer than their iterative cousins.
• Recursion can be very expensive.
• Tail recursion is sometimes cheap. Smart compilers convert it to iteration.
• Tail recursion is sometimes very expensive. Converting it by hand to iteration can be very effective.
• Guarding recursive calls can be effective.
• Handwritten stacks require lots of code yet yield little (if any) run time benefit. (Guy Steele said it best: "If the programmer can simulate a construct faster than the construct itself, then the compiler writer has blown it badly.")
• Optimization is usually effective. Enabling compiler optimization can make some little functions an order of magnitude faster. Then again, it makes some functions a bit slower.
• Timing is hard. The factor of 20 in a conditional expression is just one of many mines in this very large field."

I was a little disappointed after reading this because conditional expression is one of my favorite constructs in imperative languages like C and Java. 

In 2008 book "Beautiful Code", a collection of articles, It is  Brian Kernighan saying " recursion is a win. This fundamental programming technique almost always leads to smaller, cleaner, and more elegant code than the equivalent written with explicit loops, and that is the case here. The idea of peeling off one matching character from the front of the regular expression and from the text, then recursing for the rest, echoes the recursive structure of the traditional factorial or string length examples, but in a much more interesting and useful setting."

In the second decade of 21st century, compiler technology has improved to the extent that functional calls are pretty cheap making recursion a viable technique even in imperative languages like C, Java etc.

Single assignment feature pros and cons

In a programming language if a variable can only be assigned once and another attempt at assignment throws an error, we can say it has a single assignment feature. Prolog and Erlang are two languages with this feature I have used to write substantially involved applications like natural language processing. I believe this feature helps in avoiding errors.

In an earlier post I dealt with the problem of comparison of two equal length strings. Can we write a program for that with the restriction of using only single assignment variables?  Sure we can. Let us have an array of boolean variables. We are left with the problem of summarizing the boolean array.

public static boolean arrbooitercheck(String s1, String s2) {
  boolean [] arrboo = new boolean[s1.length()]; 
  for (int i=0; i < s1.length(); i++){

   arrboo[i]= (s1.charAt(i) == s2.charAt(i));
}

   return summarize(arrboo, s1.length());
                             }

public static boolean summarize(boolean [] arrboo, int length){
 for (int i=0; i < length; i++){ if(!arrboo[i]) return false;}  return true;                                                 }

we return false even if one character comparison is false. If that is the core of the logic of the solution, why do we even need a boolean variable? We can simply write the following.

public static boolean elegantcheck(String s1, String s2) {
   for (int i=0; i < s1.length(); i++){
if(! (s1.charAt(i) == s2.charAt(i))) return false;
      }
   return true;                  }

why are some people reluctant to write this elegant and efficient program?
Returning from the middle of a method though allowed in java, is not used by programmers initially trained in Fortran and  pascal. Recall the student was trying to code his logic into Pascal.

Thinking in terms of necessary and sufficient conditions is acquired in school math concerned with geometry. That helps in computing too.