Question 315571 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – how can I improve this recursive function? without using loops, regular expressions (regex) and other advanced language tools

The function determines the number of certain characters in a string.

function countSymbolRec(str, symbol, count) {
    if (str[str.length - 1] === symbol) count ++;
    if (str.length === 1) return console.log(count);
    countSymbolRec(str.slice(0, -1), symbol, count);
}
countSymbolRec("lkjkBBSlkl", "B", 0); // 2
Tags:

3

Answers


  1. 0

    Use indexOf!

    function countSymbolRec(str, symbol, index) {
  // Starting at `index`, find the first occurrence of `symbol` in `str`
  const symbolIndex = str.indexOf(symbol, index)
  // If `str` does not contain `symbol`, return no matches
  if (symbolIndex === -1) {
      return 0
  }
  // Otherwise, go to the next index and search again with an incremented count
  return 1 + countSymbolRec(str, symbol, symbolIndex+1)
}
console.log(countSymbolRec("lkjkBBSlkl", "B", 0)); // 2

    This has the advantage that the recursion stack will have the same number of layers as the number of occurrences of symbol on str.

    On the other hand, your implementation’s recursion stack will contain the same number of layers as the length of str.

    Compare these:

    • on the best case, a str of length L will not contain any instances of symbol. Your implementation will have a recursion stack size of L, while this solution will have a size of 1
    • on the average case, a str of length L will contain L/2 instances of symbol. Your implementation will have a recursion stack size of L, while this solution will have a size of L/2
    • on the worst case, a str of length L will be composed of only symbol characters. Both your implementation and this solution will have a recursion stack size of L

    So in most cases, the stack size of this solution is smaller than yours. This is a great improvement, specially for large strings.

    Login or Signup to reply.
  2. 0

    In addition to @enzo’s answer: you can use an internal recursive function

    function countSymbolRec(str, symbol) {
  const counter = (str, cnt = 0) => !str.includes(symbol)
      ? cnt
      : counter(str.slice(str.indexOf(symbol) + 1), cnt + 1);
  return counter(str.slice(str.indexOf(symbol)));
}

// with a slight adaption, you can count single characters 
// or substrings
function countWords(str, word) {
  const counter = (str, cnt = 0) => !str.includes(word)
      ? cnt
      : counter(str.slice(str.indexOf(word) + word.length), cnt + 1);
  return counter(str.slice(str.indexOf(word)));
}

console.log(`countSymbolRec("lkjkBBSlkl", "B") => ${
  countSymbolRec("lkjkBBSlkl", "B")}`);
console.log(`countSymbolRec("lkjCCkSlkl", "B") => ${
  countSymbolRec("lkjCCkSlkl", "B")}`);

console.log(`countWords("lkj BBBk SlkBBBl", " BB") => ${
  countWords("lkj BBBk Slk BBBl", "Bk")}`);
console.log(`countWords("lkjkBBSlkl", "B") => ${
  countWords("lkjkBBSlkl", "B")}`);
    Login or Signup to reply.
  3. 0

    You can avoid String::slice() since that’s slow (creates a new string) and pass the index to look the symbol at as an optional parameter:

    const countSymbolRec = (str, symbol, from = 0, count = 0) => 
  from === str.length ? count : countSymbolRec(str, symbol, from + 1, count + (str[from] === symbol));

['A AA CCC BBB C A', '_ ASDF AA'].forEach(str => console.log(str, '=>', countSymbolRec(str, 'A')));
    ` Chrome/120
-------------------------------------------------------
Alexander   1.00x  |  x1000000  233  242  242  245  273
OP          1.42x  |  x1000000  330  335  336  345  346
-------------------------------------------------------
https://github.com/silentmantra/benchmark `

    // @benchmark OP
{
function countSymbolRec(str, symbol, count = 0) {
    if (str[str.length - 1] === symbol) count ++;
    if (str.length === 1) return count;
    return countSymbolRec(str.slice(0, -1), symbol, count);
}

['A AA CCC BBB C A', '_ ASDF AA', 'AAAAAAAAAAAA'].map(str =>  countSymbolRec(str, 'A'));
}

// @benchmark Alexander
{
const countSymbolRec = (str, symbol, from = 0, count = 0) => 
  from === str.length ? count : countSymbolRec(str, symbol, from + 1, count + (str[from] === symbol));

['A AA CCC BBB C A', '_ ASDF AA', 'AAAAAAAAAAAA'].map(str =>  countSymbolRec(str, 'A'));
}
/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search