Project Euler 17. Questions about recursion and object lookups

Questions

Two recursive calls inside one recursive step: how bad is it?

In the code below I used some recursion, there are situations like

const somefunc = (x) => {
     //here goes some base case
         ..........
     //here goes some recursive step
          ..... return somefunc(x + 2) + somefunc (x + 4) // totally random generic example
          
}

I know that sometimes it’s really bad, like if we try to implement function like this, for fibonacci numbers:

const terribleFibs = (n) => {
  if (n === 0 || n === 1) {
    return 1;
  }
  else {
    return terribleFibs(n - 1) + terribleFibs(n - 2);
  }
}
console.log(terribleFibs(75))

It will be ridiculously slow.

However, in the code below, I used something like that, because in my case recursion won’t be really deep.
I want to know: can I use recursive calls like that sometimes, or it’s better to rewrite it with iteration? It will be more code with iteration tho.

Object lookups

I could use here only one object for lookup theoretically, but I decided to split it a little. It’s at the top of code. I would like to know, is there any difference: store all stuff in single object or split it like I did. Just for readability, I guess, my option is better.
AAnd I saw the hint page, they are using arrays of constants instead of objects, maybe I should do it too?

const singleDigitsToWord = {
    0 : 'zero',
    1 : 'one',
    2 : 'two',
    3 : 'three',
    4 : 'four',
    5 : 'five',
    6 : 'six',
    7 : 'seven',
    8 : 'eight',
    9 : 'nine'
  }
  
  const doubleDigitsToWord = {
    10: 'ten',
    11: 'eleven',
    12: 'twelve',
    '1xEnding' : 'teen',
    3: 'thir',
    4: 'four',
    5: 'fif',
    6: 'six',
    7: 'seven',
    8: 'eigh',
    9: 'nine',
    '2plusEnding': 'ty',
    20: 'twen',
    40: 'for'
  }
  
  //will be done
  const threeAndfourDigitsToWord = {
    3 : 'hundred',
    4 : 'thousand',
    'and' : 'and'
  }
  
  
  const lettersForNumber = (num) => {
    
    const len = num.toString().length
    
    //single digit number 0...9
    if (len === 1) {
      return singleDigitsToWord[num].length
    }
    
    //double digit number 10...99
    if (len === 2) {
      // 10, 11, 12
      if (num >= 10 && num <= 12) {
        return doubleDigitsToWord[num].length;
      }
      // 13...19
      else if  (num > 12 && num < 20) {
        return (doubleDigitsToWord[num.toString()[1]] 
              + doubleDigitsToWord['1xEnding']).length;
      }
      // 20, 30, 40... 90
      else if (num % 10 === 0) {
        //20, 40
        if (num === 20 || num === 40) {
          return (doubleDigitsToWord[num]
              + doubleDigitsToWord['2plusEnding']).length;
        }
        //rest of x0
        else {
          return (doubleDigitsToWord[num.toString()[0]]
              + doubleDigitsToWord['2plusEnding']).length;
        }
      }
      // all xx except the above ones:
      // 21...29, 31...39 etc.
      //21 >>> twenty one; 45 >>> forty five
      //can use recursive calls here
      else {
        let firstDigit = Number(Math.floor(num / 10) + '0');
        let secondDigit = Number(num.toString()[1]);
        return lettersForNumber(firstDigit) + lettersForNumber(secondDigit);
      }
    }
    
    //three digit number 100...999
    if (len === 3) {
      const firstDigit = Number(num.toString()[0]);
      //100, 200, 300... 900
      if (num % 100 === 0) {
        return lettersForNumber(firstDigit)
              + threeAndfourDigitsToWord[3].length;
      }
      //101...109, 401...409, 501...509 etc.
      else if (num % 100 < 10) {
        const lastDigit = Number(num.toString()[2]);
        return lettersForNumber(firstDigit)
              + threeAndfourDigitsToWord[3].length
              + threeAndfourDigitsToWord['and'].length
              + lettersForNumber(lastDigit);
      }
      // all xxx except the above ones
      else {
        const lastTwoDigits = Number(num.toString().substring(1));
        return lettersForNumber(firstDigit)
              + threeAndfourDigitsToWord[3].length
              + threeAndfourDigitsToWord['and'].length
              + lettersForNumber(lastTwoDigits);
      }
    }
    
    //TODO write code for all 4-digits after passing the tests
    //now it's just for num === 1000
    if (len === 4) {
      return 'onethousand'.length
    }
  }
  
  
  function numberLetterCounts(limit) {
    let counter = 0;
    for (let i = 1; i <= limit; i++) {
      counter += lettersForNumber(i);
    }
    return counter;
  }
   
  
  numberLetterCounts(5);

Two recursive calls inside one recursive step: how bad is it?

If it’s unnecessary, then it’s bad. If it’s the best solution, then it’s good. Sometimes it’s the best solution.

I can’t get at the Euler problem right now, internet is acting weird.

I would like to know, is there any difference: store all stuff in single object or split it like I did. Just for readability, I guess, my option is better.

My instinct would be for 1 object, but whatever works. I would have combined the first 2 objects. My main issue is inconsistent prop names, 20 is “twen” but 5 is “fif”. And why leave off the “ty”? Does that save a lot of memory?

2 Likes

well, the thing is:
I can use ‘fif’ for 50(fifty) and for 15(fifteen), when translating numerics into words, fif is kinda for this thing.

However, 20 is twenty, but 12 is not twenteen obviously, it’s twelve.
Same thing with fourteen and forty. So that’s the reason for inconsistency.

But why not just write out “fifty” and “fifteen”? I get that your object is a little smaller, but you loose a lot of readability and end up with more confusing logic. I would rather go the other direction. Maybe that’s just me. And then you have things like '1xEnding' : 'teen' and '2plusEnding': 'ty' mixed in there, which are a completely different species of data.

Do not underestimate the importance of readability. Other than “working correctly”, it is probably the most important thing. People have to come back and rearrange code months or years later and they won’t know what you were thinking. Heck, if you come back in 3 months you won’t know what you were thinking.

Good code reads like a story, a story that explains what it is doing, along with the how and why. That can be difficult. It can be especially difficult with weird little problems like this. But it is worth practicing.

2 Likes

You’re fighting two good general purpose rules of thumb here

  1. Recursion is the wrong approach, except when it’s the only sensible approach (like with graphs and trees)

  2. Don’t sacrifice readability until you have proven that you absolutely must

In this case, I would not swap from number to words to letter count, personally.

2 Likes

On that I completely agree, this stuff I can actually include in the code below, and remove from objects. don’t know, during solving problem it seemed logical, but now… yeah, these things are out of place.

That would be bigger object, I guess, and more code in the function.

Write now I am using 3 lines of code to translate numbers 30, 50, 60, 70, 80, 90.
It’s one case for all of them.

else {
          return (doubleDigitsToWord[num.toString()[0]]
              + doubleDigitsToWord['2plusEnding']).length;
        }

I guess I can write sixty, seventy etc in a lookup, and add a little more code, if it will improve readability.

I am not sure if i understood this, sorry.

I want to implement some sorting algos (merge, quick) Already coded bubble sort with iteration. For sorting problems recursion is also not good?

I am always stuck when it comes to graphs. Are there any code prep challenges, where would be appropriate to use some graphs to solve them?

  1. Recursion is the wrong approach, except when it’s the only sensible approach (like with graphs and trees)

Yeah, so true. Teachers and interviewers looooove recursion, but in the real world there is a tiny set of problems were recursion is the best approach, which the some people may never encounter. In 4 years as a professional coder, I’ve only had to write one (for a tree).

Don’t get me wrong, it’s important to learn. But don’t assume that it is always the best solution - it usually isn’t.

2 Likes

I think that would increase readability and make for simpler, easier to read code (but in all fairness, I haven’t dug deeply into your code). Yes, the object will be a tiny bit larger, but that is a single, static object. Adding a couple hundred bytes to it is not going to be a problem. We measure memory in gigabytes now. Don’t micro-optimize memory, especially at the expense of more important things. Don’t spend dollars to save pennies. In general, don’t micro-optimize. Make smart choices, but don’t worry about optimization until it becomes and issue. As the old saying, “Premature optimization is the root of all evil in programming.” We usually end up obsessing about the wrong things in the wrong ways.

2 Likes

Yeah, I know that. But I have some strange… mindset maybe. When I am typing all these properties in objects, writing each property, it feels weird, like I am typing too much. And I have this intention to use variables everytime I can. That’s why objects in the code above look like they look, with this ‘teen’ and ‘ty’ stuff.
I guess I’ll fix that with more practice.

Never heard that actually. Will keep in mind.

For my $.02, it depends. For a bubble sort, iteration makes the most sense, because you are just making passes over the list. For something like a merge sort, although the data is linear, conceptually what you are doing is a tree, like a fractal, breaking it in half which performs it’s operation on those halves, which breaks those in half to do its operation on each of those halves, that break those into halves … turtles all the way down. That is the kind of problem where recursion excels.

There are some problems (the vast majority) where iteration is clearly better. There are a tiny chunk where recursion is better. There is a frontier where things can get fuzzy. Recursion (if it’s for a problem to which it is well suited) is often cleaner and easier to read. But they also can be slower and gobble up resources. If it is an extremely large data set, I might lean into iterative if I can. And/or I might write it in a faster, more efficient language.

2 Likes

The task is

If all the numbers from 1 to given limit inclusive were written out in words, how many letters would be used?

Why convert from numbers to words when you don’t actually care about words at all? You care about letters.

2 Likes

Understood.
Well, it makes total sense.
I think now, when I have working solution, I can refactor it to work only with numbers.
The thing is: during the process of solving this, I wanted to do some logging from time to time, to make sure I build words correctly.

And I wanted to have words in the code.

I was afraid of little mistakes, like what if I used number 5 for word ‘twenty’ instead of 6. This little bugs are annoying, I wanted some defense from it.

Sure, but you could misspell ‘twenty’ just as easily.

The defense against this is to write some sort of test to validate your constants and then to never touch that data without re-validation.

1 Like

New solution(solution 2) was added to this problem just recently.
I guess it’s your solution, constants are looking just like you told :slightly_smiling_face:

I have no idea why I was not using comments like there in the constants.
Such usage of comments looks so logical and obvious now.