Scribd
Upload
6 views1 page

Recursion Master Guide

The document is a comprehensive guide on mastering recursion, particularly focusing on trees and general recursion principles. It outlines a core mindset, universal template, types of recursion, and when to use global variables versus return values. Additionally, it highlights common patterns, key rules, thinking processes, and common mistakes to avoid in recursive functions.

Uploaded by

smriti.khandelwal.73
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Recursion Master Guide

The document is a comprehensive guide on mastering recursion, particularly focusing on trees and general recursion principles. It outlines a core mindset, universal template, types of recursion, and when to use global variables versus return values. Additionally, it highlights common patterns, key rules, thinking processes, and common mistakes to avoid in recursive functions.

Uploaded by

smriti.khandelwal.73
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MASTER RECURSION GUIDE (Trees + General Recursion)

1. Core Mindset
- Every function answers ONE question
- Recursion is about values coming BACK UP
- False can be returned early, True must be verified fully

2. Universal Template
if(root == NULL) return base_value;
left = solve(left subtree);
right = solve(right subtree);
if(condition fails) return failure;
return combine(left, right, current);

3. Types of Recursion
A. Return-based (Bottom-Up): combine results from children
B. Void + Global: store answers externally (diameter, max path)
C. Backtracking: modify → recurse → undo

4. When to Use Global Variables


- When answer is not strictly from one subtree
- Example: diameter, max path sum
- Use global when multiple paths compete

5. When to Use Return Values


- When each node returns info to parent
- Example: height, BST validation, heap check

6. Going Down vs Coming Up


- Going down: exploring nodes
- Coming up: combining results (most important)

7. Common Patterns
- Validation: return condition && left && right
- Height: return 1 + max(left, right)
- Failure trick: return -1 for invalid states

8. Key Rules
- Never return true early
- Always combine left and right results
- Always handle NULL safely

9. Thinking Process
1. What should function return?
2. What do I need from left and right?
3. How to combine them?

10. Common Mistakes


- Ignoring subtree results
- Only checking current node
- Wrong base case
- Returning true too early

Final Rule
Base case → get left → get right → check current → combine results

You might also like