Recommendations for learning recursion?

I don’t know the very best resources for this, but would mostly say that having an ideal problem is often the best way to start proving this out to yourself.

You mentioned a lot of use cases, so probably picking one of those would help. I frankly fall back to recursion last when an iterative solution, often with a queue, cannot be used. Recursion has the messy issue of (in most languages without proper tail recursion and things) burning stack space, and when operating at scale that often isn’t workable. Trampolining is a technique that is rarely employed (in my experience), so stack exhaustion is a big risk.

Anyway! Let’s say you’re doing a binary tree exploration. You are passed a node that’s the root of the tree. Your exploration will either go right or left. Once you’ve picked which one, you are going to begin a search on the right or left node. This is the same work you did on the root node. The same method can be used. So now you do a search starting with left, then pick which of its children to explore and call the method with the appropriate one, and so on.

The “normal” setup for recursive functions is to have one or more base cases (null node, node with no children, node that matches search criteria) which do NOT call the method again, instead returning a terminal value and one or more recursive cases that DO call the method again with different parameters, often returning its result.

Things can get tricky when you need to construct a result based on the full recursive path, if you need to create a set of results (ie multiple matches), and plenty of other situations without a single return value determined in the base case at the deepest level of recursion. I would say that is “next step” once you gave the basics down.

You generally DO NOT want to store any external state. Your state is the current status of the stack, or possibly (like a visited set to break cycles) some state passed through as a parameter through the call chain.

I would start with something like a Binary Tree Map, where keys are the sort criteria of the map, and each node contains a value. Your node has a left node, right node, key field, and value field. The method you build is “getValueForKey” and accepts a base node and a key. It returns the value in the node with the given key, or null/empty/throw if there is no node with a matching key. Write the base cases first:

• Null node input, return null
• Null key, return null
• Key matches node key, return node value

Then the recursive case:

• Call the method itself again, returning its result, and passing the right or left node and the same key

Once you’ve built this you can write additional methods like an insert of a key/value, that returns the old value if it’s being replaced or null if it’s a new key. You can write a remove that unlinks a node (but is a little trickier, because if you’re removing a node in the middle of the tree you have to merge its children. The easiest is take the right node, then descend the right side of the left node until you get to the bottom and place the old right node there. This definitely unbalances).

Eventually you’re going to be able to enumerate base cases and recursive cases when considering these problems. Sometimes you’ll need to have an entry point method, then a recursive helper because you need to have helper parameters like the visited set that you shouldn’t require a caller to provide.

This is rambly. You’ll probably get a clearer answer asking ChatGPT.

Just saw this. If you’re still struggling maybe you can get a corvid for a study buddy: https://www.beautyofplanet.com/scientists-find-crows-are-capable-of-recursion-a-cognitive-ability-thought-to-be-unique-to-humans-and-other-primates/

The best bet to understand a recursive problem would be to debug a recursive problem using a DEBUGGER or print statements. I'd recommend using a debugger here as that would give you the working for every line of code.

I can definitely say that the moment I learn recursion I got confident in solving almost half the topics on Leetcode. Here is how I tackle a recursive problem: first look for exit condition or a base condition when you want the recursion to exit and then a recursive condition when you want the function to call itself.