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:

See all recursive problems: #recursive

See more blog posts.

Post Views: 5