1

I am teaching competitive programming for new programmers.
I want to teach about recursion, but I don't know what problem is the best for teaching about "recursion technique".

I've know many recursion problems like computing factorial, fibonacci numbers, and solving subset sum problem, and so on.
But I don't know that new programmers can understand this recursive algorithm.
Please tell me if you have a good idea of teaching recursion technique.

square1001
  • 1,402
  • 11
  • 26
  • 4
    You should teach recursion techniques by teaching recursion techniques. – jonrsharpe Nov 27 '16 at 12:48
  • @jonrsharpe, LOL, epic comment! – Lajos Arpad Nov 27 '16 at 12:54
  • start with types. show inductively defined types (lists, trees...). explain that problems with those are a natural fit to be solved with recursion. IOW, discuss how some problems are built of parts which are similar to the whole, so the searched for solution function can be applied to those parts *as if it were already written*. (see [this](https://stackoverflow.com/questions/12659581/functional-programming-lots-of-emphasis-on-recursion-why/12662393?s=3|0.0000#12662393) and [this](http://stackoverflow.com/a/19951540/849891)). – Will Ness Nov 27 '16 at 13:01
  • 1
    Please teach recursion using a problem that is best solved with recursion, instead of ruining a simple iterative solution by making it recursive. That way your students might understand why recursion is useful and when to apply it. I suggest the Towers of Hanoi or Merge Sort. Save subset sum for the dynamic programming lesson. – Matt Timmermans Nov 27 '16 at 15:19
  • Sudoku is a good example, you have to use backtracking. – maraca Nov 27 '16 at 18:42

1 Answers1

2

This is a very subjective question that might be closed, but I will answer anyway to help you.

Steps to teach recursion:

  1. Definition:

Recursion is the phenomenon when the result of a function is reused by the function itself.

  1. Notes:

    • end sign is the logical term which determines whether the function will use itself or not
    • if there is no end sign, or the end sign is always false, then we have an infinite recursion, which could lead to stack overflow
    • indirect recursion is the phenomenon, when a function is not directly using its result, but its result is a dependency of a function it calls

  2. Mathematical concepts

    • function composition is the phenomenon which occurs when a function calls another function example (the example is actually not a function composition, as correctly pointed out in the comments section): tangent(alpha) = sin(alpha) / cos(alpha)
    • recursion is a specific case of function composition, when building the dependency tree of an f function, we can find f as a dependency

  3. Examples:

    • n! (this is so simple, that we should start with this one)
    • Fibonacci
    • binary search

  4. Show what the stack is and how can a recursive function be rewritten to be iterative, using a stack of its own.

  5. Show that recursion is not always the best answer, for instance Fibonacci can be computed by a simple formula, which will yield the n's number in O(1), whilst its recursive version is exponential if unoptimized and linear if optimized, not to mention of problems of possible stack overflow on large n values.

EDIT:

As Adrian Colomitchi correctly pointed out,

tangent(alpha) = sin(alpha) / cos(alpha)

is not actually function composition. Let us not focus in this context on the language and style he used, nor his errors, let's focus on the single point in his criticism he was right. So, let us change this example to this one:

n! = n * (n - 1)!

where the function calls itself.

Another example for function composition, as shown in the comment section is:

tan(x) = div(sin(x), sin(π/2-x))

since sin(π/2-x) = cos(x)

EDIT2:

In the comment section Adrian Colomitchi pointed out that there are procedures and methods (depending on the environment one works in) which do not return values, but are still recursive. Technically he is right, but I still believe that the function-based description will be easy to understand, so the explanation of this case might be better if it could fit into the functional description.

To make the recursion lesson understandable, one could explain that they are not functions, they still function and change the state. This way this case could perfectly fit into the lesson.

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
  • "which could lead to stack overflow" noooo, not here, please!! – Adrian Colomitchi Nov 27 '16 at 12:58
  • "function composition is the phenomenon which occurs when a function calls another function example: *tangent(alpha) = sin(alpha) / cos(alpha)*" Say... what?!? Does you math high-school teacher knows how bad you got this lesson? – Adrian Colomitchi Nov 27 '16 at 13:03
  • 1
    @AdrianColomitchi, the proud lack of knowledge shown in your comment strikes me. Take a look at the basics of trigonometry and learn: https://en.wikipedia.org/wiki/Trigonometric_functions#Right-angled_triangle_definitions – Lajos Arpad Nov 27 '16 at 13:12
  • "the proud lack of knowledge shown in your comment strikes me." Oh, the irony... (which is like silvery, but with iron instead). Do you know what is the difference between function composition and an operation between two function? Does (g ∘ f )(x) = g(f(x)) sounds familiar? Penalty strike: express tan(x) as a composition of two or more functions or delete you flawed example and replace it with a correct one. – Adrian Colomitchi Nov 27 '16 at 13:54
  • 1
    @AdrianColomitchi, your first problem was that you did not believe tangent(alpha) = sin(alpha) / cos(alpha). The example was flawed indeed, but I expect some culture, fairness and most of all, correctness when one criticizes the other. I would also like to see low-rated dudes to not get arrogant above their knowledge level. And finally, I would expect all members of this site to avoid getting personal. Your third comment was actually plausible, your first lacked culture and your second lacked culture and knowledge. – Lajos Arpad Nov 27 '16 at 14:09
  • "The example was flawed indeed" it's a good sign that you admit it. take another step and correct you answer. "some culture, fairness and most of all, correctness when one criticizes the other." My apologies for that, it was a mistake. Once you correct your answer I shall delete my post. "your second lacked culture and knowledge." You seem to assume quite a lot... look at your answer, the emphasis for *tan =* belongs to you; my stylistic mistake (aside the good manners one) is that I didn't emphasize "function composition" to contrast what you intended to say and the example you used. – Adrian Colomitchi Nov 27 '16 at 14:24
  • @AdrianColomitchi, I have edited my answer. As about my comments, there is nothing to be taken back. I intend to acknowledge my mistakes whenever I do that and I am never ashamed for being wrong. On the other hand your approach to criticizing shown in your comment could scare away weaker souls from answering, questioning. Off course, if you remove your comments, I will have to remove mine as well, since they would point to dev/null. I am not angry at all, but will fight this kind of attitude with claws and teeth. As about the person, in this case you, I have no problem. – Lajos Arpad Nov 27 '16 at 14:30
  • 1
    " On the other hand your approach to criticizing shown in your comment could scare away weaker souls from answering, questioning." You have a good point here, I'll pay a special attention to it in the future. – Adrian Colomitchi Nov 27 '16 at 14:35
  • 1
    Regarding your edit: may I suggest you do something to signal the flaw earlier than the very end? If you don't want to replace the example there, at least mark it somehow visible (I'm not mistaken, SO's markdown supports `` tags). If you don't want to strike it, make is smaller (use `/` tags) and put a "footnote mark". In any way, do something earlier, don't wait for the end of your post for correction: many may stumble on that error and abandon reading through half of you points. As for `tan` as composition, how about `div(sin(x), sin(π/2-x))`? – Adrian Colomitchi Nov 27 '16 at 14:44
  • @AdrianColomitchi and I will pay attention to my examples in the future, as my initial example could have misled people. If there are no other observations about the answer, then let's close this discussion and let's make sure we will get alon better the next time. I, for one will try that. – Lajos Arpad Nov 27 '16 at 14:44
  • @AdrianColomitchi, you have a two good points there, I have edited my answer, making sure that if its first half is read, then there will be no misleadings and added your example as well. – Lajos Arpad Nov 27 '16 at 14:53
  • Cool. No hard feelings on my side either. A good day ahead for the rest of the weekend. – Adrian Colomitchi Nov 27 '16 at 14:56
  • 1
    Another improvement that may be applied to your answer: recursion is not *limited* to a particular case of function composition. Think the 8-queens problem - or any other tree-exploration problem - you can use recursion and, theoretically, have an exhaustive set of all solutions without defining the problem as function composition (i.e. the Pascal procedures/Fortran subroutines - function which return nothing - can still call themselves recursively). – Adrian Colomitchi Nov 27 '16 at 15:07
  • Good point. Thinking about the state of mind of young lads and girls making their first steps in programming I attempted in my answer to make an explanation of these (void functions in C, methods in Java, procedures in Pascal, Subs in Basic) so that it could fit into the grounds of the functional description since they still change the state (even a small procedure only calling itself will change the state, as the infinite cycle will certainly affect the behavior). – Lajos Arpad Nov 27 '16 at 15:18