You have a set of stairs. You can only move one or two steps at a time. Calculate how many possible combinations of moves can be made to traverse the exact number of steps, for any given total number of steps.

^ yes it can, but that is a memorized solution that you likely wouldn't implement if you hadn't seen it before. i'm sure they don't use recursion on clients and i'm not exactly sure what this problem says about the interviewer other than "he doesn't leet".

It's actually a pretty simple dynamic programming problem you can solve using constant space, do it iteratively rather than recursively. Check it out of LeetCode.