The correct way to implement a feature is with plugin. Especially if you aren't using a custom theme.
This was not always the case. For example some years ago (even still today) you could download a theme which would come with a ton of extra features but all those features would be embedded in code throughout the theme itself. This created a lot of lock-in to the theme. If users wanted a new theme, entire huge chunks of data and functionality would be lost because it was embedded as part of the previous theme.
The moral of the story is, if you are building some code that could be useful no matter what theme you use, then put it in a plugin.
Any code that is very directly related to just the theme itself that doesn't really make sense as usable with other themes, keep in the theme folder.
The benefit of putting code in a plugin is that you can reuse it as needed pretty easy when you build more sites. If you make it generic enough, you could eventually distribute it as a standalone tool that others could use.