Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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 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.

linkedin
github
slack

Post Views: 5
Posted in ReviewTagged #recursive, review

Post navigation

LeetCode: Word Search
LeetCode: Word Search II

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.