Recursion is when a function calls itself. That sounds circular, but it works because each call handles a smaller version of the same problem. Eventually the problem is so small it can be answered directly. That direct answer is called the base case, and it is what stops the chain of calls.
You are standing at the back of a queue and you want to know how many people are ahead of you. You cannot see the front. So you tap the person in front of you and ask: "How many people are ahead of you?"
That person does not know either. So theyy tap the person in front of them and ask the exact same question. This keeps going, person by person, until someone at the very front says: "Nobody is ahead of me. Zero."
Now the answers pass backwards. The person behind the front says "0 + 1 = 1". The next says "1 + 1 = 2". Each person adds one to whatever they were told, and passes it back. Eventually the answer reaches you.
There are 4 people. You are person D at the back. Watch the question travel forward one person at a time, then the answers travel back:
Notice two things:
1. A base case - Person A at the front. They stop the chain and give a direct answer. Without a front person, the question would travel forward forever.
2. A recursive case - Everyone else. They pass the same question forward (a slightly smaller version of the problem, since there are fewer people ahead) and combine the answer when it comes back.
That queue you just pictured? The computer does the exact same thing when a function calls itself. Each person in the queue becomes a stack frame - a record of one function call, holding its parameter values and where to return to when it finishes.
Just like the queue: each frame waits for the one it created to finish. The newest frame is always on top. When it finishes, it is removed, and the one underneath picks up where it left off. The first frame created is the last to finish - exactly like person D waiting at the back.
Let's turn the queue into code and see that it is the same picture:
def people_ahead(person):
if person is None: # base case: nobody here
return 0
return 1 + people_ahead(person.next) # 1 for this person + restint peopleAhead(Person* person) {
if (person == nullptr) // base case: nobody here
return 0;
return 1 + peopleAhead(person->next); // 1 for this person + rest
}int PeopleAhead(Person person) {
if (person == null) // base case: nobody here
return 0;
return 1 + PeopleAhead(person.Next); // 1 for this person + rest
}int peopleAhead(Person person) {
if (person == null) // base case: nobody here
return 0;
return 1 + peopleAhead(person.next); // 1 for this person + rest
}Each person in the queue is now a function call. Each function call is a frame on the stack. Watch the stack grow one frame at a time as the question travels forward, then shrink one frame at a time as the answers come back:
def countdown(n):
if n == 0: # base case
print("Go!")
return
print(n, end="... ") # do something
countdown(n - 1) # recursive call (smaller problem)void countdown(int n) {
if (n == 0) { // base case
cout << "Go!";
return;
}
cout << n << "... "; // do something
countdown(n - 1); // recursive call (smaller problem)
}void Countdown(int n) {
if (n == 0) { // base case
Console.Write("Go!");
return;
}
Console.Write(n + "... "); // do something
Countdown(n - 1); // recursive call (smaller problem)
}void countdown(int n) {
if (n == 0) { // base case
System.out.print("Go!");
return;
}
System.out.print(n + "... "); // do something
countdown(n - 1); // recursive call (smaller problem)
}Calling countdown(3) prints: 3... 2... 1... Go!
Same pattern as the queue. Each call is a person joining the line:
Just like the queue: countdown(3) started first but finished last. countdown(0) was the base case - it finished first, and the rest unwound one at a time behind it.
Imagine you are organising a family reunion and you need to count how many living relatives you can invite. You cannot do it all at once. Instead, you ask your Mum: "count everyone on your side who can come." Then you ask your Dad: "count everyone on your side who can come." Each of them does the same thing - they ask their own parents. Eventually someone has no living parents to ask, and that person just reports back "1" - themselves. Each person waits for both answers, adds 1 for themselves, and passes the total back up.
This is the key difference from Level 1. In the queue and countdown examples, each call onlyy made one recursive call and waited for one answer. Here, each call makes two recursive calls - one for mum's side, one for dad's side. It makes the first call, waits for that entire side to finish, then makes the second call and waits for that to finish too. Only then can it add everything together.
def count_family(person):
if person is None: # base case: nobody here
return 0
left = count_family(person.mum) # count mum's side
right = count_family(person.dad) # count dad's side
return 1 + left + right # me + both sidesint countFamily(Person* person) {
if (person == nullptr) // base case: nobody here
return 0;
int left = countFamily(person->mum); // count mum's side
int right = countFamily(person->dad); // count dad's side
return 1 + left + right; // me + both sides
}int CountFamily(Person person) {
if (person == null) // base case: nobody here
return 0;
int left = CountFamily(person.Mum); // count mum's side
int right = CountFamily(person.Dad); // count dad's side
return 1 + left + right; // me + both sides
}int countFamily(Person person) {
if (person == null) // base case: nobody here
return 0;
int left = countFamily(person.mum); // count mum's side
int right = countFamily(person.dad); // count dad's side
return 1 + left + right; // me + both sides
}Read that return line as: "To count everyone starting from this person, I need the total from mum's side and the total from dad's side, then I add 1 for myself." The function cannot compute its total until both recursive calls have finished and returned their answers.
You
/ \
Mum Dad
/ \
Gran Gramps
5 people. You has Mum and Dad. Mum has Gran (her mother) and Gramps (her father). Dad has no living parents to ask - both his mum and dad pointers are null. Gran and Gramps also have no living parents to ask. We call countFamily(You) and expect the answer to be 5.
When someone has no living parents to ask, both their mum and dad pointers are null. The function calls countFamily on both, and both immediately return 0 (base case: no one here). That person then computes 1 + 0 + 0 = 1 and returns - they are counting just themselves.
The same stack rules from Level 1 apply here. The stack grows as calls are made and shrinks as they return. The difference is that when a call gets an answer back from its first recursive call (mum's side), it does not finish yet. It still needs to make its second recursive call (dad's side), wait for that answer, and only then can it compute its total.
Phase 1 - Going down mum's side. The function always calls countFamily(person->mum) first, so we follow that path as deep as it goes.
Phase 2 - Back at Mum. Gran's side answered 1. Now calling Gramps' side.
Phase 3 - Back at Mum. Both sides are done.
Phase 4 - Back at You. Mum's side answered 3. Now calling Dad's side.
Phase 5 - Back at You for the last time. Both sides are done.
Notice the pattern: each call that is not a base case makes its first call (mum's side), waits for it to fully resolve, then makes its second call (dad's side) and waits again. Mum's entire side - all the way down to the leaves and back - finishes completely before Dad's side even begins.
In a tree, each node can have a left child and a right child. To process the whole tree, you need to visit both sides. That means each call makes two recursive calls instead of one - exactly like countFamily in Level 2.
def height(root):
if root is None: # base case: empty tree
return -1
left = height(root.left) # height of left subtree
right = height(root.right) # height of right subtree
return 1 + max(left, right) # 1 for this node + max of childrenint height(TreeNode* root) {
if (root == nullptr) // base case: empty tree
return -1;
int left = height(root->left); // height of left subtree
int right = height(root->right); // height of right subtree
return 1 + max(left, right); // 1 for this node + max of children
}int Height(TreeNode root) {
if (root == null) // base case: empty tree
return -1;
int left = Height(root.Left); // height of left subtree
int right = Height(root.Right); // height of right subtree
return 1 + Math.Max(left, right); // 1 for this node + max of children
}int height(TreeNode root) {
if (root == null) // base case: empty tree
return -1;
int left = height(root.left); // height of left subtree
int right = height(root.right); // height of right subtree
return 1 + Math.max(left, right); // 1 for this node + max of children
}Read that return line as: "My height is 1 (for the edge connecting me to my parent) plus whichever of my two children is taller." Just like countFamily, we cache the results from both recursive calls first, then use them to compute the final answer.
Each node asks its left child and right child the same question. Leaves have no children, so both their calls hit the base case and return -1.
return 1 + max(height(root.left), height(root.right))return 1 + max(height(root->left), height(root->right));return 1 + Math.Max(Height(root.Left), Height(root.Right));return 1 + Math.max(height(root.left), height(root.right));This is functionally identical to the version above. Both recursive calls still happen - left first, then right - but the results are not stored in variables. The compact version is common in production code, but the cached version makes it clearer that there are two separate recursive calls happening in sequence.
5
/ \
3 7
/
1
Phase 1 - Starting at the root (node 5). We always go left first, as far as we can.
Phase 2 - Back at node 1. Its left child has answered (-1). Now it needs to check its right child before it can compute its own result.
Phase 3 - Back at node 3. Its left subtree is fullyy explored and returned 0. Now it needs to check its right child.
Phase 4 - Back at node 5 (the root). Its entire left subtree has been explored and returned a height of 1. Now it needs to explore the right subtree.
Phase 5 - Back at node 7. Its left child answered -1. Now it checks its right child.
Phase 6 - Back at node 5 (the root) for the last time. Both subtrees are fully explored.
Some problems need to carry information down through the calls. Instead of building an answer on the way back up, you modify a value on the way down and check it when you reach a leaf.
Given a tree and a target sum, return true if any root-to-leaf path adds up to the target.
def has_path_sum(root, target_sum):
if root is None: # base case: no node here
return False
target_sum -= root.val # subtract this node's value
if root.left is None and root.right is None: # leaf?
return target_sum == 0 # did we hit exactly zero?
return (has_path_sum(root.left, target_sum) or
has_path_sum(root.right, target_sum))bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) // base case: no node here
return false;
targetSum -= root->val; // subtract this node's value
if (!root->left && !root->right) // leaf?
return targetSum == 0; // did we hit exactly zero?
return hasPathSum(root->left, targetSum) ||
hasPathSum(root->right, targetSum);
}bool HasPathSum(TreeNode root, int targetSum) {
if (root == null) // base case: no node here
return false;
targetSum -= root.Val; // subtract this node's value
if (root.Left == null && root.Right == null) // leaf?
return targetSum == 0; // did we hit exactly zero?
return HasPathSum(root.Left, targetSum) ||
HasPathSum(root.Right, targetSum);
}boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) // base case: no node here
return false;
targetSum -= root.val; // subtract this node's value
if (root.left == null && root.right == null) // leaf?
return targetSum == 0; // did we hit exactly zero?
return hasPathSum(root.left, targetSum) ||
hasPathSum(root.right, targetSum);
}Read this as: "Subtract my value from the remaining target. If I am a leaf and the target is now zero, we found a valid path. If not, ask my left child or my right child if they can finish the job."
|| (or) do here?The || operator means: try the left side first. If it returns true, stop immediately and return true (no need to check the right side). If the left side returns false, then try the right side.
So the function explores the left subtree first. Only if no valid path exists on the left does it try the right subtree.
5
/ \
3 7
/
1
Phase 1 - Starting at the root (node 5). We go left first, just like the height example.
Phase 2 - Back at node 3. The left child returned false. Because of the || operator, the function now tries the right child to see if there is a valid path on that side.
Phase 3 - Back at node 5 (the root). The entire left subtree returned false. The || operator now tries the right subtree.
Phase 4 - Back at node 5 for the last time. Both subtrees have been fullyy explored.
Now let's try with targetSum = 9. The path 5 -> 3 -> 1 adds up to 9, so we expect the function to find it.
Phase 1 - Same as before, we go left from the root.
Phase 2 - A true has been found! The || operator short-circuits: since the left side returned true, there is no need to check the right side at any level. The true travels straight back up the stack.
|| finds a true on the left side, it does not bother checking the right. The true bubbles all the way back to the root without exploring any further.
height(3) and height(7) run, they each have their own root. They do not interfere with each other.true, the right call is skipped entirelyy.