# Recursive linear search - branch style and layout

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.

• 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)); – ZeroStatic Sep 11 '14 at 10:00
• 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? – dcorking Sep 11 '14 at 11:01
• 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) – ZeroStatic Sep 11 '14 at 11:33
• I wish I could accept all the answers. I learned a lot from all of them. – dcorking Sep 12 '14 at 6:57

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.

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));
}
}

• Your second way, while using less stack space, makes $2n - 1$ calls to containsA in the worst case, compared to $n + 1$ calls in the original. – mjolka Sep 11 '14 at 11:50
• @mjolka: Yes, if you implement recursion correctly for these kind of theoretical implementations, you get that effect. – Guffa Sep 11 '14 at 12:35

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

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

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 ();


if (a) {

• I didn't realize I could replace a code block with a single statement, so thank you. Is a single-line if idiomatic? – dcorking Sep 11 '14 at 11:44