Recursion is a problem solving technique, where solutino of a larger problem is defined in terms of smaller instances of itself.

**Basic Abstractions**

Name | Summary |
---|---|

Recursive function | Visualize a larger problem into a smaller one of the exact same type |

Terminating condition | Function stops calling itself when the terminating condition is reached |

Head recursion | When recursive call is made before it performs its own task |

Tail recursion | When recursive call is made after it performs its own task |

Tail recursion vs iterative loop | tail recursion can be easily re-write in form of a loop |

// 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**

**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: Sort List
- Leetcode: Reaching Points
- Leetcode: Pow(x, n)
- Leetcode: Path Sum III
- Leetcode: Nested List Weight Sum II
- Leetcode: Nested List Weight Sum
- Leetcode: Maximum Depth of N-ary Tree
- Leetcode: Maximum Binary Tree
- Leetcode: Lowest Common Ancestor of a Binary Tree
- Leetcode: Letter Case Permutation
- Leetcode: Flatten Nested List Iterator
- Leetcode: Factor Combinations
- Leetcode: Count Complete Tree Nodes
- Leetcode: Closest Binary Search Tree Value
- Leetcode: Brace Expansion II
- Leetcode: 24 Game

See more blog_posts.