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 [display-posts tag=”recursive” posts_per_page=”100” orderby=”title”]
See more blog_posts.
