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

minesweeper: auto reveal of zero field. (I guess you know what I mean) It's a kind of floodfill.

- Depth-first search (e.g., solving the 8-queens problem).
- Alpha-beta search (e.g., chess).

Display all files under a certain directory.
Implement the A* algorithm.

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

List all files in a directory. Then list all files in all subdirectories of that directory.

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.

Learn Haskell, or just about any functional language.

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

I'm suprised noone mentioned Towers of Hanoi. I've only seen a non-recursive solution like once and it was pretty ugly.
As mentioned Scheme is probably your best bet if you want to get used to recursion since from my understanding you can't avoid using it with that language.

Quote:

Original post by daviangel I'm suprised noone mentioned Towers of Hanoi. I've only seen a non-recursive solution like once and it was pretty ugly.

On odd-numbered moves, the smallest disk rotates from A->B, from B->C, from C->A, etc. On even-numbered moves, the only possible move that does not involve the small disk happens. It's not that hard, but it's easier to do recursively, that's true.

Quote:

Original post by daviangel I'm suprised noone mentioned Towers of Hanoi.

I've always felt that Towers of Hanoi are one of those things nobody really knows about or has any relation to and the only time it's brought up is in CS courses. And by the time rules are explained, the solution is often provided alongside to make them completely clear.

Similar to Fibonacci. Duh - sum 2 values, repeat, what better than a for loop.

Compared to saying: "checkers" or "chess" or "tic tac toe".

Quote:

Original post by Antheus Similar to Fibonacci. Duh - sum 2 values, repeat, what better than a for loop.

Ah, this is sometimes better:


(Thanks for the link, apatriarca)

And fast exponentiation with an integer exponent can be implemented recursively too. :)

[Edited by - alvaro on July 2, 2010 5:22:13 PM]

Quote:

Original post by alvaro (I need to figure out how to use TeX notation)

This is off-topic. I don't think TeX is supported in this forum, but you can give a try to this web service.

Any task that employs a "divide and conquer" strategy. Binary search, for example (similar to binary tree but not exactly the same). Skimming an algorithm book I have for "divide and conquer", I find closest pair problem, examples of solving polynomials, Strassen's method for matrix multiplication, and the fast Fourier transform.

Here's an example for marking a foot ruler.

void rule(int l, int r, int h){ int m = (l+r)/2; if (h > 0) {  mark(m,h);  rule(l,m,h-1);  rule(m,r,h-1); }}

Assume that "void mark(int x, int h)" makes a mark h units high at position x.

Quote:

Original post by LessBread void rule(int l, int r, int h){ int m = (l+r)/2; if (h > 0) { mark(m,h); rule(l,m,h-1); rule(m,r,h-1); }}

A quick question: doesn't declaring 'm' inside the recursing function increase the memory usage of the recursion? I try to avoid using variables if their scope includes the recursing function (thus a 'new' version of them would be created over and over again).

Quote:

Original post by alvaro Quote: Original post by Antheus Similar to Fibonacci. Duh - sum 2 values, repeat, what better than a for loop. Ah, this is sometimes better: (Thanks for the link, apatriarca) And fast exponentiation with an integer exponent can be implemented recursively too. :)

Fibonnaci numbers in O(log(n)) time seems to be a common CS problem, but I was surprised to learn that it's actually possible in constant time*. The matrix exponentiation can be reduced to exponentiation of constants through finding its eigenvalues. Neat tibit for the day.

*I assume that pow() functions are constant time, but I guess I don't really know.

Quote:

Original post by Antheus I've always felt that Towers of Hanoi are one of those things nobody really knows about or has any relation to and the only time it's brought up is in CS courses.

Not so for me [smile].
My grandma actually had a small toy one: Three poles on a base with a few discs of differing sizes (probably only about 5 discs). Someone explained the puzzle to me and before long I worked out how to manually solve it. This was some time between the ages of 5 and 10 (a few decades ago), well before I ever had an interest in computer programming.
The Fibonacci example you touched on is an interesting one as it is a very good example of where recursion is not only the less than optimal solution, but it's downright abhorrent in terms of its Big-Oh notation, vs an iterative approach.

Quote:

Original post by LessBread Any task that employs a "divide and conquer" strategy. Binary search, for example (similar to binary tree but not exactly the same).

Binary search is not one I would use as a good example of where recursion should be used, because it is more simply solved through iteration. But one could certainly do it that way for learning. The example code posted is a very good example.

Quote:

Original post by szecs A quick question: doesn't declaring 'm' inside the recursing function increase the memory usage of the recursion? I try to avoid using variables if their scope includes the recursing function (thus a 'new' version of them would be created over and over again).

Yes it does, and avoiding unnecessary variables in the stack frame of the recursive function is a very good idea as it certainly improves both the maximum recursion depth and the execution speed.
However in a case such as the above, there is no way to avoid it because the value of m is needed for the second recursive call upon eventual return from the first one.

Quote:

Original post by iMalc Yes it does, and avoiding unnecessary variables in the stack frame of the recursive function is a very good idea as it certainly improves both the maximum recursion depth and the execution speed. However in a case such as the above, there is no way to avoid it because the value of m is needed for the second recursive call upon eventual return from the first one.

As I can see it, it could be rewritten like this:

void rule(int l, int r, int h){  if (h > 0)  {    mark((l+r)/2,h);    rule(l,(l+r)/2,h-1);    rule((l+r)/2,r,h-1);  }}