In case you've ever struggled with recursion, the structure that my teacher taught me forever ago that has alway led me right: You want to do three things, always, in a specific order: * Terminate (check to see if you're done, and just return) * Iterate (increment/change some val) * Recurse
theres no joke here, it's just how you can cruise control to working recursive code, which is often very useful, even if there are probably better ways to do it. If you remember to terminate first, and recurse last, and try really hard to keep that consistent, usually the problem shakes out easy.
I remember learning Computer Science in the ancient days, and learning recursion. At first, of course, it lived up to the name; I would curse, and then re-curse, and then re-curse several more times until the thing worked!
Recursion can be your friend. Unless you are recursing a b-tree. (Not a binary tree, which is easy, but a b-tree found at the heart of large data stores.) even then, once you have worked it out it is easier the second time. In the end, the rules still apply.
It’s still recursion if the recursive call is first (prefix or head recursion) or in the midst of processing (infix). For example, some search and data structure traversal algorithms depend on the distinction. (Eg. Infix recursion of a BST visits the nodes in sorted order).