Review: Recursive Problems

Posted on January 30, 2018September 3, 2019 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

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

See more blog_posts.

Post Views: 5