Recursive linear search - branch style and layout

Question

Is my layout of the if/else statement reasonable?

It feels clumsy to me to spread the termination condition over the first three lines of the function. Can I squeeze it into one or two lines? Would it help if I used the ternary operator? How can I make the JavaScript more idiomatic (while still using recursion)? Any other improvements?

var containsA = function(sentence) {
 if (sentence.length == 0) {
 return false;
 }
 else {
 return sentence[0] === 'A' || containsA(sentence.substr(1));
 };
};

var containsA = function(sentence) {
 if (sentence.length == 0) {
 return false;
 }
 else {
 return sentence[0] === 'A' || containsA(sentence.substr(1));
 };
};
// Unit tests
var assert = function(code) {
 if (eval(code)) {
 document.write(code + " test passed.<br>");
 }
 else {
 document.write(code + " test FAILED.<br>");
 };
};
assert("!containsA('')");
assert("containsA('A')");
assert("!containsA('a')");
assert("containsA('HAH!')");
assert("!containsA('carrots')");

I have simplified details that are not relevant to my question. This simpler version attempts to reimplement String.prototype.contains(). If I convert my string to an array I could use Array.prototype.find() but my hunch is that would be less readable.

• ZeroStatic: Combining everything into one ternary seems even clumsier looking to me. I'd stick with mjolka's answer. return sentence.length == 0 ? false : (sentence[0] === 'A' || containsA(sentence.substr(1))
• dcorking: In Ruby, I can write return false if sentence.length == 0 as a tidy way to put the termination condition in one line. Does Javascript offer a one-line equivalent to block-structured if?
• ZeroStatic: A non-block structured if :') if(sentence.length == 0) return false; That's pretty much the only thing I can think of. (Right now, at least)
• dcorking: I wish I could accept all the answers. I learned a lot from all of them.

Answer 1

How can I make the JavaScript more idiomatic?

By using indexOf:

var containsA = function(sentence) {
 return sentence.indexOf('A') != -1;
};

---

As your update specified that you want to use recursion, let's see what we can do.

Cleaning up, we can remove the else (and the extraneous semi-colon).

var containsA = function(sentence) {
 if (sentence.length === 0) {
 return false;
 }
 return sentence[0] === 'A' || containsA(sentence.substr(1));
};

Or you can write it more succinctly, but I would say at the cost of readability

var containsA = function(sentence) {
 return sentence.length > 0 &&
 (sentence[0] === 'A' || containsA(sentence.substr(1)));
};

Now we could end up creating a lot of substrings. To avoid this, we can pass an index into the string

var containsA = function(sentence, i) {
 i = i || 0;
 if (i >= sentence.length) {
 return false;
 }
 return sentence[i] === 'A' || containsA(sentence, i + 1);
};

Or

var containsA = function(sentence, i) {
 i = i || 0;
 return i < sentence.length &&
 (sentence[i] === 'A' || containsA(sentence, i + 1));
}

---

In case this is not homework or a thought exercise...

Don't do this. By using recursion (and substr) to solve this, you're simultaneously making your code less efficient, in terms of both time and memory, and less readable. As @Guffa pointed out, it may even blow the stack.

The function containsA has no reason to exist. Just use indexOf where appropriate.

Answer 2

If you want to process the string that way, you shouldn't use recursion at all. What you are doing is simply a loop disguised as recursion:

function containsA(sentence) {
 while (sentence.length > 0) {
 if (sentence[0] == 'A') return true;
 sentence = sentence.substr(1);
 }
 return false;
}

If you want to do recursion you should split the work into equal smaller parts instead of shaving off a single character at a time, so that you won't be doing recursion as deep as there are characters in the string:

function containsA(sentence) {
 if (sentence.length <= 1) {
 return sentence == 'A';
 } else {
 var middle = sentence.length / 2;
 return containsA(sentence.substr(0, middle)) || containsA(sentence.substr(middle));
 }
}

• mjolka: Your second way, while using less stack space, makes \2ドルn - 1\$ calls to containsA in the worst case, compared to \$n + 1\$ calls in the original.
• Guffa: @mjolka: Yes, if you implement recursion correctly for these kind of theoretical implementations, you get that effect.

Answer 3

Based on your question in the comments you could do the following:

var containsA = function(sentence) {
 if (sentence.length == 0) return false;
 return sentence[0] === 'A' || containsA(sentence.substr(1));
};

Of course people will always have different opinions, but here's a few other statements supporting the use (or non-use) of braces.

Note that these are not Java/JavaScript specific. (But since the syntax of the actual subject is similar, I feel they still apply)

Other stackexchange questions regarding if-else coding style:

https://softwareengineering.stackexchange.com/questions/16528/single-statement-if-block-braces-or-no

Accepted Answer:

....Therefore, I prefer to just put everything on one line if it's sufficiently short and simple:

if(condition) statement;

https://stackoverflow.com/questions/1434760/one-line-if-statements

Highest rated answer:

if you should really use one line if

if(condition) statement=new assignment; will be better since its one line, it should contain one operation.

Other sources:

http://www.gnu.org/prep/standards/standards.html

One of various samples (note the lack of braces for the single-statement conditional):

For the body of the function, our recommended style looks like this:

if (x < foo (y, z))
 haha = bar[4] + 5;
else
 {
 while (z)
 {
 haha += foo (z, z);
 z--;
 }
 return ++x + bar ();
 }

http://www.mono-project.com/community/contributing/coding-guidelines/

Avoid using unnecessary open/close braces, vertical space is usually limited:

good:

if (a)
 code ();

bad:

if (a) {
 code ();
}

Unless there are either multiple hierarchical conditions being used or that the condition cannot fit into a single line.

• dcorking: I didn't realize I could replace a code block with a single statement, so thank you. Is a single-line if idiomatic?
• Federico J.: I wouldn't do that. It tends to make your code error prone.
• ZeroStatic: Sentiment on several questions asked on stackexchange sites is that curly braces have the biggest preference, but short functions / 1 line conditionals can be used in cases like yours. And they MUST be placed behind the if clause to maximize readability if you insist on using this style.
• dcorking: I like the answer's quotes from style guides, even if from C# and C. Relevant SO: stackoverflow.com/questions/8860654/…