Hi,
I am having problems thinking in recursive terms for solving a problem? Can you guys suggest some problems which are a fit for recursive domain ?
- Reverse a link list
- Factorial
- Sum of digits of a number.
Cheers!
Excercises in recursion
Just implement a binary tree. Insert into or find an element in a binary tree is one of the most classic examples.
Implement Quicksort
-me
Implement Quicksort
-me
minesweeper: auto reveal of zero field. (I guess you know what I mean) It's a kind of floodfill.
-The map function on a linked list
-The map function on a binary tree
map should take a function (call it f) and a data structure (linked list or binary tree in these cases) and should return a new data structure with the same layout but with every element replaced with f(element). So if we have the list [1,2,3] and we call map on that list and the function square (which multiplies a number by itself), it should return [1,4,9]. If it's on a tree, it should return a tree with the same structure, just with the element changed.
Other related functions you could write are filter and fold (aka. reduce).
Look up the text book "Structure and Interpretation of Computer Programs" (it's available free online through the MIT Press) and a large portion of the exercise questions will involve recursion.
-The map function on a binary tree
map should take a function (call it f) and a data structure (linked list or binary tree in these cases) and should return a new data structure with the same layout but with every element replaced with f(element). So if we have the list [1,2,3] and we call map on that list and the function square (which multiplies a number by itself), it should return [1,4,9]. If it's on a tree, it should return a tree with the same structure, just with the element changed.
Other related functions you could write are filter and fold (aka. reduce).
Look up the text book "Structure and Interpretation of Computer Programs" (it's available free online through the MIT Press) and a large portion of the exercise questions will involve recursion.
1) Print all permutations of a string.
2) Print all subsets of a set. You can represent a set as a string. For example, for "AB" it should print the empty string, A, B and AB.
2) Print all subsets of a set. You can represent a set as a string. For example, for "AB" it should print the empty string, A, B and AB.
I always like to suggest something where recursion isn't just the way one could do it, but is really the most sensible way to do it.
For example Factorial can be calculated recursively, but for practical purposes nobody would sensibly do that. Same with the other examples posted by the OP.
Binary tree insertion or searching can be done recursively, but there is no need to since a simple loop is better. Self-balancing is another story though.
The algorithms that have to use recursion (or fallback to implementing an explicit stack - yuck) are those that make at least two recursive calls.
I would recommend implementing quicksort, or mergesort
For example Factorial can be calculated recursively, but for practical purposes nobody would sensibly do that. Same with the other examples posted by the OP.
Binary tree insertion or searching can be done recursively, but there is no need to since a simple loop is better. Self-balancing is another story though.
The algorithms that have to use recursion (or fallback to implementing an explicit stack - yuck) are those that make at least two recursive calls.
I would recommend implementing quicksort, or mergesort
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
