Recursive Functions for Beginners?

Question

I'm looking for a few recursive function examples, preferably ones that show increase in complexity. I understand basic recursive functions, but I'm having trouble implementing them in my code. I've never used them in my code before, and I know it doesn't always call for it, but I'd like to try. Is there a good resource with examples, and maybe challenges of some sort? Or even some simple math problems (Project Euler-style?) that I could use recursion on?

For examples, I prefer C#, but anything works.

Answer 1

1 the easiest ones are factorial, Fibonacci sequences, or any mathematical sequence defined by recursive functions.

2 then you can move to

any algorithms that use a depth first search.

E.g. tree traversal, graph traversal,

search problems, like 8-queens problems.

3 you'd probably like to study divide and conquer algorithm, e.g. merge sort and quick sort. they are usually implemented recursively.

These are all very classical!

Answer 2

I found the online courses made available by the Stanford Engineering Everywhere program to be an excellent resource. If you look at their CS106B course, lectures 7 through 11, you should have a good basic understanding of recursion. They also provide exercises with problems to solve.

http://see.stanford.edu/see/lecturelist.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e

Answer 3

Well, if you are having trouble implementing basic recursive functions, I'd suggest that you don't actually understand them. But there's no shame in that, not everyone 'gets' recursion readily. Rather than butt your head against the simple algorithms I'd suggest you try:

• Thinking about, and studying the uses of, recursive data structures such as trees, graphs or lists. Learning to use recursion in situations where recursion is the natural approach is probably a better route to recursive joy than trying lots of examples which ought, really, to be tackled with loops.
• Using a language in which recursion is a basic, primitive, concept. Haskell and some of the other functional programming languages would do. Oft-times the most natural way to tackle a problem with FP is to implement recursion; in other languages you often have to struggle first with the language's weird approach to recursion. Whether C# has a weird approach to recursion I do not know.