Count number of sub string recursively

An algorithm to recursively count the number of sub string present in the given string in javascript.

Example

Input:
'learnersbucket'
'e'

Output:
3

count substring recursively

Implementation to recursively count the number of sub string in the given string

  • We will check if the length of the original string is less than n1 == 0 or less than the substring n1 < n2, we will return 0.
  • Then we will check if there is a sub string match the given sub string in the original string.
  • If it is present then we will call the same function by removing the substring and increasing the count.
  • Else we will call the recursively same function to find sub string from one letter after the current.
let countSubString = (str, subStr, n1 = str.length, n2 = subStr.length) => {
  //If the string is empty
  //Or less than substring
  if(n1 === 0 || n1 < n2){
    return 0;
  }
  
  //Check if there is a subString in the original string
  if(str.substring(0, n2) === subStr){
    //Remove the substring from the original string and call the function with increased count
    return countSubString(str.substring(n2), subStr) + 1;
  }
  
  //Call same function with one letter less than original string
  return countSubString(str.substring(1), subStr);
}
Input:
console.log(countSubString('learnersbucket', 'e'));

Output:
3

Time complexity: O(n).
Space complexity: O(n) (Call stack).

Working of above function

countSubString(){
   //3
   return countSubString(){ //1st index
     //2
     return countSubString(){ //5th index
        //1
        return countSubString(){ // 12th index 
          //0
          if(n1 === 0 || n1 < n2){
             return 0;
          }
        } + 1;
     } + 1;
   } + 1;
}