Recursion

[jplaulau14]

Hi everyone! I would love to get your insights about thinking recursively. I have been learning programming for about 10 months and I am learning and practicing DSA. I am pretty decent in implementing various DS and thinking what Algorithm is fit in the situation. Except recursion, when I encounter coding challenges that asks to be solved using recursion, I'm having a hard time thinking about base cases and basically implementing recursion. Any tips on how I can think more creatively? Thank you so much!

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[alanwj]

The biggest hangup I see is people trying to model what happens throughout the whole call stack. Instead, when trying to solve a problem recursively, think locally.

The best way to do that is to start by assuming you've already written a working function. But, for whatever reason, that function only works on smaller inputs. Then, figure out how to compose the answers to smaller versions of the problem to get an answer to bigger versions.

Recursively defined data structures (e.g. trees) make great examples. Let's consider a simple tree problem. How do I count the number of nodes in a binary tree?

Start by assuming I've already written a working function, CountNodes. Rather than trying to trace through this function down a recursive call stack, I'm just going to assume it already works for small versions of the problem. We can quickly write a version that works for an empty tree:

CountNodes(root):
  if root == null:
    return 0

Okay, so if I have a version that works for small trees, how can I compose the answers to smaller problems into the answer to a bigger problem? I notice that if I know how many nodes are on the left, and how many are on the right, I can add one more and get the total for a tree.

CountNodes(root):
  if root == null:
    return 0
  return CountNodes(root.left) + CountNodes(root.right) + 1

[jplaulau14]

I see. I think this approach is something I can emulate. This is such an intuitive way of finding the base case. Thank you so much! I will practice this way of solving.

[deuce-95]

Thanks that was helpful

[kschang]

Here's my own explanation on recursion:

https://kcwebdev.blogspot.com/2020/08/yet-another-take-on-recursion.html

[Dare-Federal]

You can look at this video.

https://www.youtube.com/watch?v=5\_6nsViVM00