Review: Recursive Problems Posted on January 30, 2018July 26, 2020 by braindenny Recursion is a problem solving technique, where solutino of a larger problem is defined in terms of smaller instances of itself. Basic Abstractions Num Name Summary 1 Recursive function Visualize a larger problem into a smaller one of the exact same type 2 Terminating condition Function stops calling itself when the terminating condition is reached 3 Head recursion When recursive call is made before it performs its own task 4 Tail recursion When recursive call is made after it performs its own task 5 Tail recursion vs iterative loop tail recursion can be easily re-write in form of a loop 6 Count Complete Tree Nodes Leetcode: Count Complete Tree Nodes // traverse a linked list // head recursion void traverse(Node* head) { if head != NULL { traverse(head->next); printf("%d", head->data); } } // traverse a linked list // tail recursion void traverse(Node* head) { if head != NULL { printf("%d", head->data); traverse(head->next); } } Never miss the terminating condition, else the function may fall into infinite recursion. Scenarios Code Skeleton Top Questions Name Example Recursive vs DP Key Questions: What are your base cases? How you get f(n) from f(n-1)? How to evaluate the complexity: time and space? For nested problems, we can use recursive to simplify the logic. Flatten Nested List Iterator The most impressive problems to me: Count Complete Tree Nodes Flatten Nested List Iterator Super Pow Reaching Points See all recursive problems: #recursive Review: Recursive ProblemsLintCode: Digital ProblemLeetCode: Stone Game IILeetCode: Soup ServingsLeetCode: Sort ListLeetCode: Reaching PointsLeetCode: Pow(x, n)LeetCode: Path Sum IIILeetCode: Number of Steps to Reduce a Number to ZeroLeetCode: Nested List Weight Sum IILeetCode: Nested List Weight SumLeetCode: Minimum Distance to Type a Word Using Two FingersLeetCode: Maximum Depth of N-ary TreeLeetCode: Maximum Binary TreeLeetCode: Lowest Common Ancestor of a Binary TreeLeetCode: Letter Case PermutationLeetCode: Implement Magic DictionaryLeetCode: House Robber IIILeetCode: Flatten Nested List IteratorLeetCode: Factor CombinationsLeetCode: Count Complete Tree NodesLeetCode: Closest Binary Search Tree ValueLeetCode: Brace Expansion IILeetCode: Binary Tree Upside DownLeetCode: Binary Tree Coloring GameLeetCode: 24 Game See more blog posts. Post Views: 5