Recursive Functions for Beginners?

4
votes

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.

3
recursion
Keep monitoring this page for some examples: stackoverflow.com/questions/2621726/… - Amadiere
If you are new to software development, more important is to avoid recursion where it is not suitable. - Pavel Radzivilovsky
Begin: Wiki this. GOTO BEGIN - user1228
I have a theory that many students are afraid of recursive functions because when teachers introduce the subject they say most students are afraid of recursions. (I am not trying to be clever) - Kobi
Search for "recursion" on Google and check out spell corrector's message. Is that a Google joke? - Nick Dandoulakis

3 Answers

3
votes

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!

2
votes

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

0
votes

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.