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:

See all recursive problems: #recursive

- Review: Recursive Problems
- LintCode: Digital Problem
- LeetCode: Stone Game II
- LeetCode: Soup Servings
- LeetCode: Sort List
- LeetCode: Reaching Points
- LeetCode: Pow(x, n)
- LeetCode: Path Sum III
- LeetCode: Number of Steps to Reduce a Number to Zero
- LeetCode: Nested List Weight Sum II
- LeetCode: Nested List Weight Sum
- LeetCode: Minimum Distance to Type a Word Using Two Fingers
- LeetCode: Maximum Depth of N-ary Tree
- LeetCode: Maximum Binary Tree
- LeetCode: Lowest Common Ancestor of a Binary Tree
- LeetCode: Letter Case Permutation
- LeetCode: Implement Magic Dictionary
- LeetCode: House Robber III
- LeetCode: Flatten Nested List Iterator
- LeetCode: Factor Combinations
- LeetCode: Count Complete Tree Nodes
- LeetCode: Closest Binary Search Tree Value
- LeetCode: Brace Expansion II
- LeetCode: Binary Tree Upside Down
- LeetCode: Binary Tree Coloring Game
- LeetCode: 24 Game

See more blog posts.