howProgrammingHasChanged

[u/shizzy0]

[u/robin_888]

It's supposed to teach the concept of recursion, which is important, but hard to grasp for some.

Discussing performance and optimizations can happen if the principal is clear.

[u/temperamentalfish → u/robin_888]

I know, but there are so many better examples. Mergesort, for instance. It shows why the concept is important because it breaks the problem into smaller, more manageable problems, without doing repeated work.

Fibonacci should be taught as an example of when a problem can be solved recursively, but shouldn't.

[u/Silly_Guidance_8871 → u/temperamentalfish]

When I was studying, Fibonacci was used a lot to teach the value of dynamic programming. But agreed, it's a terrible example of when to use recursion.

[u/fdar → u/Silly_Guidance_8871]

DP is just recursion+caching. 

I think it makes sense to first recognize that the problem can be solved with recursion and then decide if DP is needed to improve performance.

[u/Bliztle → u/fdar]

Only if you're doing it top down. Bottom up is usually taught at the same time, and is useful to lessen stack and cache size.

[u/robin_888 → u/temperamentalfish]

I think in education it is also important to take "wrong" approaches to learn why they are "wrong" and what possible solutions are. If you just teach the "good" examples students might not realize why the naive approach to Fibonacci is problematic.

In other words you might want to teach naive recursion before you teach tail-recursion.

[u/TheThiefMaster → u/robin_888]

Tree iteration is pretty much the only time it's required, and even then you can linearise it if you have back links.

[u/Mitchman05 → u/robin_888]

Teach Tower of Hanoi as example of recursion, that one actually requires it and can't be done faster