Jump to content
  • Advertisement
Sign in to follow this  
_korg

Excercises in recursion

This topic is 3079 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
minesweeper: auto reveal of zero field. (I guess you know what I mean) It's a kind of floodfill.

Share this post


Link to post
Share on other sites
- Depth-first search (e.g., solving the 8-queens problem).
- Alpha-beta search (e.g., chess).

Share this post


Link to post
Share on other sites
-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.

Share this post


Link to post
Share on other sites
List all files in a directory. Then list all files in all subdirectories of that directory.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!