Understanding Recursion for Elegant Solutions

Ryan Yu at Web Directions Developer Summit 2025

Recursion’s Three Essential Ingredients

Ryan Yu introduces recursion as a function calling itself and isolates its three essential ingredients: self-invocation, a base case, and a recursive case with changing input. He demonstrates them with a sumRange function that adds the integers from a supplied number down to one.

Watching Recursion Unwind on the Call Stack

Ryan traces sumRange(5) through the JavaScript call stack, showing how each invocation creates an execution context. Once the base case returns one, the suspended calls unwind in reverse order and combine their results to produce 15.

Stack Overflow and the Iterative Alternative

Ryan demonstrates how an unreachable base case or unchanged recursive input produces unbounded calls and eventually a stack overflow. He then compares recursive and iterative implementations, arguing that the right choice depends on readability and the problem’s structure rather than syntax alone.

Modeling Maximum Depth in a Binary Tree

Ryan introduces a binary tree and frames maximum node depth as a problem well suited to recursion. Using depth-first search and post-order traversal, he derives a zero-returning base case for missing nodes and a recursive case that selects the deeper branch.

Maximum Depth, Frame by Frame

Ryan executes the maximum-depth algorithm step by step through the call stack, first resolving leaf nodes and then combining left and right subtree depths with Math.max. The concise recursive solution finds a depth of three while preserving the same asymptotic time and space behavior as its longer iterative counterpart.

Backtracking Through a Subset Tree

Ryan turns to backtracking as a strategy for problems with unknown-depth branching. He represents every subset of [1, 2, 3] as a path through a decision tree in which each value is either excluded or included, then explains how the algorithm retreats to explore alternative paths.

Implementing Include–Exclude Recursion

Ryan builds the subset generator with two recursive branches, an index-based base case, and arrays that track the current path and completed results. He walks through execution contexts, bookmarks where calls resume, copies completed paths with slice, and removes choices with pop to perform backtracking.

Where Recursive Search Becomes Elegant

Ryan completes the traversal and compares its complexity with an iterative subset solution. He highlights permutations, N-Queens, Sudoku, and Android unlock patterns as branching searches where recursive decision points express the possibilities cleanly, then closes by restating recursion’s three defining elements.

Hi, everybody. I hope everybody's having a great day today. And I am Ryan Liu. And let's talk about recursion. So we as a developer and engineers, we may have heard of recursion before, and some of you might have used it before. But for many, recursion is still a mysterious. It's because we don't fully understand how it actually works.

And you may have tried this before, but some kind of infinite loop happened and your browser was frozen. So I'm not going to never use this again. So you just forget about this recursion. So in this session, we're going to deep dive into recursion. So we will start with a quick example of how the recursion works. And then we'll be getting into a couple more advanced examples to see how recursion can help solve some complex problems.

So at the end of this session, I hope we have a better understanding of how the recursion works and you can confidently use it in your own code. So let's take a look at this long definition. I got it from MDN and we don't really like to read this long definition. So let's focus on those three key elements.

So recursion is a function calling itself, and it has a base case which ends the recursion, and it has a recursive case with a different input to resume the recursion. So basically this is it. We have a function calling itself, and we have to set the base case and a recursive case. But to understand a bit better, let's take a look at a quick example. So we have a sumRange function here.

So this function accepts a number and it adds up from one to up to the number we passed. For example, if we passed five, it's gonna be like five plus four plus three plus two plus one. So let's take a look at it. So we have a function calling itself. So if you look at this return statement, we are actually not only returning the number, but also we are actually returning the function itself. So it's calling itself here.

And then we have a base case which ends the recursion. So when the number reaches one, then we actually return the value and a normal function call and it actually ends the chain. And finally, we have a recursive case here with a different input. So eventually we're going to hit the base case and we can get out of this recursion.

The base case and a recursive case are most important parts here because if we don't set it right, It's gonna cause infinite loop and finally it's gonna cause the stack overflow. And we're gonna actually take a look at this visually why this is happening. So let's put them on the left side and on the right hand side, we're gonna take a look at JavaScript engine.

So we have a call stack here and when the JavaScript is called, execution context is created there and when it starts to return the value, it's gonna pop off the stack. So let's take a look, some range five. So let's send five there and we're going to call this function so it's invoked. So it's going to create new execution context there with some range five.

Now we're going to go to the next line, but the current value is five, so it's not going to meet the base case because to meet the base case number has to be one. So it's going to skip to the next line and then let's log our return statement here. So we have a current number five plus and then we have recursive case here, some range this time with a different input four.

So this is our recursive case with a different input and then we're going to call some range again. So Because we're going to call this again, it's going to be added to the call stack again. And it's going to skip this base case because it doesn't meet the base case. And we have another return statement here.

And then again, we are calling itself again and then going up. And it's going to add to the call stack. And I'm going to skip this still yet to meet yet. And we have another return statement. And I think you can guess where we are getting it to, right? So we have another instruction context created in the code sec and then we have return statement here.

And then finally, we have some range one. Now the interesting part happening here, right? Now it hits the base case because the current number is one and it now returns one, right? And then there's no more a function call, so it will start to return this value. Because it's returning the value, this specific execution context is going to be part of the stack.

So it's going to be gone. And this one is the returned value of some range one. So if we visualize it, it's going to look something like this. And then now some range two is a two plus one, which is three. And again, this is the returned value. It's going to be part of the stack.

And this is the return value of someRange2. So it's going to look more like this visually. It's going to be 6, and again, popping off the stack, go to next line, and it's going to be 10, and popping off the stack again, and it will be like this.

And finally, we hit our initial poll, and then we can find the final answer, which is 15. And obviously, we return this 15, so this execution context is going to be top of the stack. So we found this number to use recursion. So basically, like, recursion is a function calling itself, and then we set the base case and also recursive case.

So to keep calling itself until it missed the base case, and once it missed the base case, and we actually stop the chain and then return the value, and finally we hit our initial code. Now let's take a look at the infinite loop and why this is happening, right? So let's go back to the moment right before we hit the base case.

So we're going to change this code a little bit so we will never meet this base case, or we will change our recursive case so instead of sending different input, we will always send same input. So that means it will never meet the base case.

So there is no scenarios that we can get out of this loop and it will keep going and again and again. And it will finally hit the memory limit in the browser. And in the older browser, the browser is going to be frozen. But in modern browser, there is a maximum call so that it will actually get out of it and then send you the error message. So that's basically recursion, right?

So if we go back to the app, we call this call stack because we have this call, this is called stack overflow because we have a call stack and it's going over our stack. So we call it like stack overflow. So if we go back to the definition again, I hope this time it makes a bit more sense.

We have a function calling itself here. And then we set the base case to end the recursion. And then we have recursive case with a different input to resume this recursion. And then you might ask like, hey Ryan, I'm pretty sure we can write each recursive solution, right?

This is kind of like, you know, is it right each recursive solution? And the answer is yes, right? If we put it in the iterative solution, it's going to look something like this and it may look more straightforward and intuitive for many. And they share the same time complexity O of n and space complexity O of n linear as well.

So they are sharing the same time and space complexity, then is it getting more of like a dx, right? So which one is more makes sense for you and for your team and then you which one actually provides more intuitive approach. But some more complex scenarios, actually, recursion can provide more elegant solution than iterative solution. So let's take a look at two more bit advanced examples. So first one is for clarity and readability.

So in some scenarios, actually, recursion can provide more intuitive and straightforward solution than iterative solution. And we're gonna take a look at calculating max node depth. The other example we're gonna take a look at is for unknown depth branching. So there are some scenarios that we have to make some decision points. And if we are not sure how much deep down we have to go, then Recognt actually can provide much better solution than iterative solution.

So for this example, we're going to take a look at backtracking. So first, let's go with calculating max node depth. Now today here, some of you might be very advanced, some might be less advanced. So to make sure everybody's on the same page, I will quickly go through some fundamental definitions.

So please bear with me if you already know all those concepts. So let's take a look at this tree structure and this is a binary tree. So binary tree has at most two children, one on the left and then one on the right. So if we look at 10 at the very top root node, there is two children, 5 and 15.

And if you look at 15, there are two children, 12 and 20. So this is a binary tree. And if we write this class with the constructor, it's gonna look something like this. And the tree shape is gonna look something like this. So we have at the very top, 10 there. And then it has a left side, which has 5 there.

And then it has right inside, which has 15 there. And the 15 has two children as well, one on the left, which is 12, and then 20 on the right hand side. So let's actually focus on calculating max node depth. So today we're gonna use Recursion and we're gonna use DFS and post order. So DFS stands for depth first search.

There's the other breadth first search, but we're not gonna go into too much details of this. But let's focus on DFS and this is a way to explore nodes as deep as possible, right? And with the post order, we're going left first and there we come back and then do the other parts. So with the DFS and post order with the recursion, we're gonna look at five first on the left hand side and we're gonna go down and 12, 20 and coming back 15, and 20.

So that's the order we're going to look at the node. Now, as a human, it's kind of very straightforward, right? So the answer is 3 because 10, 15, 12 is the next depth node, 3, or like 15, 20, which is 3 as well. But we have to write algorithm to find this answer.

So we're going to use recursion. To find the answer. So to write the recursion, we got to find base case and recursive case. So let's find that out. So if we revisit this, our tree structure here, and when we look at five, it has no children anymore. So left, no, right, no as well.

So we now can see that, oh, if there is no values, then there is no more that we need to travel down. So we can actually exit out of it and then we can go back. So this is going to be our base case. And when it hits the base case, we're going to return zero. And then when it hits the base case, we're going to go up. And when we do that, we're going to do one plus.

So we know we have one node down there. And for the recursive case, We have two directions coming up. So when you look at root node 10, we are coming up from 5, but there's another direction coming up from 15. And then we will choose a higher number between those 5 and 15 so that we don't have to care about the low number because we only wanted to find the maximum depth.

So we're gonna use math.max, sorry, max, max, and then we're going to choose bigger number between left and right. And this is going to be our recursive case. So if we put this into our code, it's going to look something like this. And that's it. This is our code to find the max node depth.

As we discussed, this is going to be our base case, and this is going to be our recursive case. And let's take a look at how it works visually in our call stack again. So we will start with max def 10. So 10 is not like actual number, it's this, you know, node starting from 10.

So let's start from here. And the next line is our base case, but because we have value down the, down the, the left and right hand side, we have a five and a 15, no three there. So we're gonna skip this and let's log our return statement. And we will tackle the left hand side first, five, and like DFS and post order, we're gonna go to the left deep down first, and we're gonna add new execution context there.

And this is gonna return another return statement like this. And then again, we're going to take the left side first. So this is going to create a new execution context. And now it hits the base case because we are sending null value and we're going to return zero. And because it's returning the value now, the execution context for it is going to be pop of the stack.

And then this zero is going to be going like, if we see it visually. And then this we know is going to return zero, so we're going to go through all the call stack again. And this is going to be zero. Now with math max 0, 0 is a zero. And then it's become like simple mathematics, like 1 plus 0 is 1, and 1 is the return the value of max step five.

So it's going to go like this. So we found one from the left hand side. Now let's take a look at the right hand side here, right? And it's going to create new execution context and the return statement will be like this. And then left hand side first, so max depth 12 is going to be created as an execution context in the stack.

And we have a return statement like this. And we are actually repeating the same process, right? So we have maxStepNull, which returns 0, and now it's popping off the stack, and then it will return the value like this. And we know this value is going to be 0, so let's just add a 0, and Mathf.Max will be 0, and 1 0, is one and it's going to be returned here.

And we found one from the node 12. Now we know 20 is going to be the same story as 12, so it will be one as well. And this is going to have like one and one plus one is two. And two will be the return value of max step 15. So it's gonna visually move it like this.

And then now we found one from the left hand side and a two from the right hand side. And from here, this is gonna be two because two is higher than one. And finally, we found our answer, three, from our initial call. So this is basically like using recursion to find this no max, def. So again, we calling the function itself, we set the base case, and we have recursive case.

And time complexity of this is O of n, and space complexity is O of log n here. And if we write this as iterative solution, it's gonna be longer than recursion because we have to check every single decision that when that's the recursive case is happening.

So those two different solutions are gonna share same time and space complexity. But obviously, if we understand recursion and how it all works in the call stack and with the execution context, recursion actually can provide the shorter and more so we took a look calculating node depth.

And then now let's take a look at the backtracking example. Now, backtracking is very complex, and I don't expect we totally understand this backtracking within like 10 minutes of time. But I think it's gonna be a great opportunity for us to see how the recursion actually can provide and help solve some complex problems like using backtracking.

So backtracking is a technique that we actually go deep down first and then we do the validation. And once that's done, we actually redoing what we have done with the current step and then come back up, kind of like backtracking and then try other path. And for this example, we're gonna find the subset of this input, all right? So we have one, two, three, and we wanted to find all the possible subset of this array.

And we will use backtracking to find this. So let's visualize it, right? So we have at the very top, we have like empty array. So our starting point is empty array. And we will start with current value, which is one. And we will go to the left-hand side, which is gonna exclude, and right hand side, which we're gonna include.

So what I mean by include and exclude is when we go to the left hand side, we're gonna exclude whatever the current value is. At the moment, it's one, but on the right hand side, we're gonna include one. So let's visualize what I mean by that. So we're going to left hand side, so we are not gonna include our current value.

But on the right hand side, we're gonna include it, so it's gonna be one. Now we go to the next level and it is gonna be the same story. Left, nothing's gonna be included, but on the right hand side, we're gonna include current value, which is gonna be two. And the other side, the same is not gonna include, so it's gonna be just one, but it's gonna be one and two.

And on the last level, it's gonna be the same story like this. And here two and two, three and on so on. And when you look at the last leaf nodes there, this is the answer that we wanted to find out. So to find out, we actually need to have empty array as a start point. And then we will travel down there.

And once we find this value, we're going to add it to result. And then we've done the exclude and we will do the include, which is going to be three. So we're gonna add three. And once we done exclude and include the parts, we're gonna go back up and then we will try another path. So that's backtracking. And we're gonna add two there and then two, three and so on.

So let's find out our base case at recursive case. So this is gonna be our recursive case. So unlike before, we had only one recursive case, this time we're gonna have two recursive case. And then for base case, when the I is out of the total length of the input array, so that's going to be our base case. So let's put that at the very top there.

And then we have core stack here, and this is our complete example. So we have input 1, 2, 3, and we're going to track of current, and we're going to track of the result as well. And we're going to return this result at the end of the process. So now we have a subset and we will start with the DFS and starting with the zero there.

And we're gonna go up here and it's not meeting the base case because the current I is zero but what we want is three to meet this base case. So we're gonna go to the next line. And this is our first recursive case, our exclude parts. And we're gonna bookmark it so that when we come back down here later, we know where to resume.

So let's bookmark this here. And then new execution context is gonna be created and we're gonna go up here and we will see if we're submitting the base case, no, then we're gonna go to the next. But again, we're gonna see another exclude recursive case and it's gonna be added there and it's gonna repeat again until we meet the base case here. So finally we meet the base case and we're gonna add whatever current value is to our result like this.

And then we add the empty array and we found first result here. And we add current value. We don't add current value straight away to the result because we always gonna add and remove the current value. So it will get always changed. So we actually need to save the copy of the current value.

So we add a slice method there. And then it's gonna return, we are not returning any value or anything, so it's just a return so that the execution context is gonna be top of the stack, and then we resume from there. So we go next line, and we're gonna push the current value, which is gonna be three, and now we hit another recursive case.

This time it's include, right? So as you can see from the tree, we actually found the one, and now we are trying include the part, which is a three. So we change the bookmark there and then we add new execution context there. And we hit the base case and we add the current value three and we found here like this, right?

And we return and popping off the stack and we resume from here, right? And then we redo what we have done. So we pop it. And this is backtracking happening, and the current value will be empty array, and it's gonna be part of the stack. Now, we start from here, we bookmarked exclude there, and then we push the current value, which is gonna be two, and then as you can see, we actually went to the other path on the right hand side, and then we're gonna start this, you know, calling function call again. And it's going to be the same story that this time we're going to go to the left exclude and we're going to push the current value, which is 2, this one, and then we're going to return like this.

And then we started from there and then push 2-3 and then this time we're going to check the include parts and it's going to be added to the result as well. So this time we found two or three. So this is basically like how the backtracking with the recursion works, right? So we started from include, like we backtracking and popping the current value, and then we have another include here.

We go back up, and then we do backtracking one more time, and then finally we reach to the root node, and then we will explore the other parts like this. So like this. So this way, we can actually explore deep down first, and then we come back up and then try the other path. And if we put it into iterative resolution, it's gonna look something like this, and their time complexity is the same.

Over 2 to the N times N. And space complexity is a bit different. The recursion is linear, but the iterative solution is a bit more complex. Because this subset example has only two decision points, maybe there are not much difference between recursion and iterative solution.

But for more complex examples, for example, like permutations and queens, Sudoku, Android, you know, unlock patterns. Like, you know, if you have, like, Android phone, you know, you are actually do the patterns, right? So if you think about it, there are so many different possibilities of doing, like, patterns, right? And it's almost impossible to write all the possibilities of the patterns with the iterative solution.

In the case, you know, we set the base decision points with the recursive case, and then we let them, you know, loop in again and again and again. And we just set the base case to get out of the chain when it meets the moment that we have to get out. That is recursion. So I hope it gives you kind of understanding of how the recursion works, right?

So it's a function calling itself with the base case and the recursive case with a different input. And I hope you can use this recursion in some cases. And if you can remember those three elements, it's going to help you a lot when you actually go to that line that if you have to write to recursion.

Thank you so much. I am Ryan Niu and yeah, let's connect on LinkedIn. I'm available at LinkedIn. I am Ryan Niu. Thank you.

Recursion

What is Recursion?

The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).
— MDN

What is Recursion?

function sumRange(num) {
  if (num === 1) return 1;

  return num + sumRange(num - 1);
}

The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).
— MDN

The sequence isolates the three essential parts of recursion, then maps them to the example: sumRange calls itself, num === 1 is the stopping condition, and sumRange(num - 1) continues with a smaller input. A final warning emphasizes that the base and recursive cases must be defined correctly to avoid infinite recursion and stack overflow.

function sumRange(num) {
  if (num === 1) return 1;

  return num + sumRange(num - 1);
}

sumRange(5); // 15

A function calling itself

A base case

A recursive case

Infinite loop

Stack overflow

An execution-stack diagram traces sumRange(5) as calls for 5, 4, 3, 2, and 1 are pushed onto the JavaScript call stack. At the base case, sumRange(1) returns 1; the stack then unwinds, combining the pending additions until the original call returns 15. A contrasting failure state shows that if the base case is never met or the recursive input does not change, calls continue through zero and negative values until the call stack overflows.

What is Recursion?

function sumRange(num) {
  if (num === 1) return 1;

  return num + sumRange(num - 1);
}

The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).
— MDN

What is Recursion?

function sumRange(num) {
  if (num === 1) return 1;

  return num + sumRange(num - 1);
}

The act of a function calling itself, recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion).
— MDN

The recap progressively connects each part of the definition to the code: the recursive call invokes sumRange again, the condition returning 1 ends the recursion, and the argument num - 1 advances each recursive call toward that base case.

Can we use iterative solutions?

Recursive

function sumRange(num) {
  if (num === 1) return 1;

  return num + sumRange(num - 1);
}

Iterative

function sumRange(num) {
  let sum = 0;

  for (let i = num; i > 0; i--) {
    sum += i;
  }

  return sum;
}

For Clarity and Readability (Calculating node depth)
For Unknown Depth/Branching (Backtracking)

In certain cases, recursion can be more straightforward and more readable than iterative approaches.

When the search depth or branching is unknown, recursion is well-suited because each recursive call naturally represents a new decision level.

The sequence first presents the recursive sumRange, then adds an equivalent loop-based implementation for comparison. It concludes by identifying two situations where recursion can offer a more natural solution: readable traversal such as calculating node depth, and searches with unknown depth or branching such as backtracking.

For Clarity and Readability (Calculating node depth)
For Unknown Depth/Branching (Backtracking)

Calculating node depth

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

Recursion (DFS - PostOrder)

Depth-First Search

A way to explore all nodes of a tree by going as deep as possible along one branch, before coming back and exploring others.

Traverse the left subtree, then the right subtree, and finally process the current node after both children are done.

function maxDepth(root) {
  if (root === null) return 0;
  return 1 + Math.max(
    maxDepth(root.left),
    maxDepth(root.right)
  );
}

Time complexity: O(n)

Space complexity: O(log(n))

The sequence introduces a binary tree rooted at 10, with left child 5 and right child 15; node 15 has children 12 and 20. It then develops a post-order depth-first solution: recursively find the left and right subtree depths, return zero for a null node, and return one plus the larger subtree depth. Call-stack diagrams trace evaluation from maxDepth(10) through the leaf and subtree calls until the function returns a maximum depth of 3.

function maxDepth(root) {
  if (root === null) return 0;
  return 1 + Math.max(
    maxDepth(root.left),
    maxDepth(root.right)
  );
}

Time complexity: O(n)

Space complexity: O(log(n))

function maxDepth(root) {
  if (root === null) return 0;

  let maxDepth = 0;
  const stack = [[root, 1]];

  while (stack.length > 0) {
    const [node, depth] = stack.pop();

    if (node) {
      maxDepth = Math.max(maxDepth, depth);
      stack.push([node.left, depth + 1]);
      stack.push([node.right, depth + 1]);
    }
  }

  return maxDepth;
}

For Clarity and Readability (Calculating node depth)
For Unknown Depth/Branching (Backtracking)

2. For Unknown Depth/Branching (Backtracking)

Backtracking

Backtracking is a technique where recursion explores a path, and if it doesn’t lead to a valid solution, it undoes that step and tries another path.

Backtracking

Input: [1, 2, 3]

Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

An include-or-exclude decision tree demonstrates how backtracking generates every subset of [1, 2, 3]. Starting with an empty set, each input value creates two branches: exclude it or include it. Repeating this choice for 1, then 2, then 3 produces eight leaf nodes representing all possible subsets. The traversal records a leaf as a result, returns to the preceding decision, and explores the alternative branch.

function subsets(nums) {
  const result = [];

  const dfs = (i, nums, current) => {
    if (i === nums.length) {
      result.push(current.slice());
      return;
    }

    dfs(i + 1, nums, current);

    current.push(nums[i]);
    dfs(i + 1, nums, current);
    current.pop();
  }

  dfs(0, nums, []);
  return result;
};

Time complexity: O(2ⁿ * n)

The sequence traces the recursive subset algorithm for input [1, 2, 3]. The first recursive call excludes the current value; the second includes it after current.push(nums[i]). When the index reaches the input length, a snapshot made with current.slice() is added to the results. The call-stack examples follow the exclude path to [], include 3 to produce [3], backtrack with current.pop(), and continue through branches producing [2] and [2,3]. A final comparison shows this recursive solution beside an iterative subset-building solution; both are labelled O(2ⁿ * n) time.