Public Group

# 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.

## 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 ?

- Factorial
- Sum of digits of a number.

Cheers!

##### Share on other sites
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 on other sites
minesweeper: auto reveal of zero field. (I guess you know what I mean) It's a kind of floodfill.

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

##### Share on other sites
Display all files under a certain directory.
Implement the A* algorithm.

##### 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 on other sites
List all files in a directory. Then list all files in all subdirectories of that directory.

##### 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 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

1. 1
2. 2
3. 3
Rutin
20
4. 4
khawk
14
5. 5

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633655
• Total Posts
3013187
×