I remember learning recursion twice: once for Fibonacci and once for Hanoi. It did take a while to click but it unlocked recursion schemes and dynamic programming.

To me it was an example that there are some problems only solved by recursion but that they also overblown in their relevancy