7
$\begingroup$

Normally, Java 2 is a prerequisite for my Computer Architecture course. I gave permission to a strong student who has only taken Java 1 to take Computer Architecture, provided that she learn the basics recursion over the summer. (In Computer Architecture, the student write recursive programs in assembly language.) Can anyone recommend a free online source where she can pick up, and ideally practice, elementary recursion? The only language she knows is Java.

Update

I modified my question to make more clear that I am only asking about elementary recursion. (I teach about recursion, in depth, in a more advanced course, Programming Languages, in the functional programming unit.)

I ended up recommending to the student:

Improve this question
$\endgroup$
11
  • $\begingroup$ Recursion is not a language specific concept. Recursion in java is like recursion in any other procedural language. Have them write a method to compute factorials, as a classical first example. For kicks, have him write a recursive tree walker to display a directory structure, and then componentize it by separating the generic tree walker code from the visitor that operates on the directory structure $\endgroup$
    – pojo-guy
    Jul 3, 2017 at 14:24
  • $\begingroup$ I understand it's not language dependent, but it's easier to learn something in a familiar language and programming environment if possible. $\endgroup$
    – Ellen Spertus
    Jul 3, 2017 at 14:43
  • 3
    $\begingroup$ See this question: cseducators.stackexchange.com/questions/1380/… $\endgroup$
    – Ellen Spertus
    Jul 3, 2017 at 22:54
  • $\begingroup$ Base case @EllenSpertus, base case. That should be if(you aren't here) {see the question cseducators.stackexchange.com/questions/1380/…} $\endgroup$
    – Buffy
    Jul 4, 2017 at 8:55
  • $\begingroup$ Java does not fully support recursion (same for a lot of other languages), as it does not have tail call optimisation. It will not struggle with algorithms where the call depth is O(log n). However infinite recursion is impossible. Check to see if it is possible in scalla. I have heard that the problem is in the JVM, however scalla may get around this by using trampolinning (A technique to simulate tail call recursion). $\endgroup$
    – ctrl-alt-delor
    Jul 4, 2017 at 16:38

6 Answers 6

Reset to default
4
$\begingroup$

For learning recursion...

A student with some programming experience might just need a brief tutorial. Since I teach CS50 AP, I make use of CS50 Study which has a page dedicated to recursion here. There is a slideshow with speaker notes as an overview, tips and tricks for using recursion, and sample problems with solutions. The language in question is C, but any student who knows Java will find the syntax familiar. Additionally, on YouTube the Computerphile video on recursion is excellent as a supplement to this page.

For practicing recursion...

I'm a bit surprised this hasn't come up already, but CodingBat has a handful of recursion exercises in Java ranging from the most basic to some that are quite challenging. There are two sections of problems: Recursion-1 and Recursion-2. The site doesn't have much in the way of a tutorial (other than solutions to the first two exercises), so it's mainly useful as a practice tool. The nice thing for an instructor is that students can log in to track their progress. If you do want the student to complete x number of problems, you can verify completion by having her either print out her progress while logged in or share her account with you so you can see what has been completed from the teacher view.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Often times, google is our best of friends (I hope). A rather simple search leads to a very informative site:

http://introcs.cs.princeton.edu/java/23recursion/

It is very thorough, and explains many use-cases for recursion.

Another very handy resource is, inevitably, Stack Overflow: this question also provides some information, but it is rather specific. Instead of staying there, one can navigate to the Related Questions section, and from there choose a promising question (usually the one with the highest votes, but not always) and reading it. And so on, and so on... (recursively ;)).

Improve this answer
$\endgroup$
1
  • $\begingroup$ @nocomprende well the exit statement is a simple check: student.getLearntSubjects().contains("Recursion"); $\endgroup$
    – ItamarG3
    Jul 6, 2017 at 11:36
3
$\begingroup$

Eric Roberts wrote a great little book: Thinking Recursively. Hard to do better than that. He's a master.

Whoa. Not cheap. Disclaimer - I'm not him and he doesn't give me kickbacks.

I'll try to add something free, but you, the prof, should get a copy.

https://duckduckgo.com/?q=programming+recursively may be all you need, actually.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I hadn't known about that book, and I'm an Eric Roberts fan. Thanks! $\endgroup$
    – Ellen Spertus
    Jul 3, 2017 at 14:23
  • $\begingroup$ Note, for the record, that the first (classic) version of the book uses Pascal for the examples. $\endgroup$
    – Buffy
    Jul 3, 2017 at 16:23
  • $\begingroup$ Ooh! It's on Safari Books, where I have a subscription. $\endgroup$
    – Ellen Spertus
    Jul 3, 2017 at 18:37
1
$\begingroup$

This doesn't answer your question, but might be a resource for your course.

Back when (don't ask) Scot Drysdale (Dartmouth) and David Levine (Saint Bonaventure) had a great exercise for assembly language:

Animal

Write an assembly language program whose execution results in writing a true copy of itself elsewhere in memory and then executing the copy.

A refinement is to erase (zero out) the original.

It is recursion without a base case, of course, though you could trick it up.

However you can also give it a payload, which could be nasty, so beware and discuss.

It is also an example, in assembly, of a Quine

Great fun too (sans payload).

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is an excellent answer to a question that I did not ask. Why don't you ask that question and use this answer? (It's okay to answer your own question.) $\endgroup$
    – Ellen Spertus
    Jul 6, 2017 at 14:11
1
$\begingroup$

Sorry for another answer that doesn't fully answer your question, but I have found that the following explanation helps some students so much that they need less practical excercises to understand recursion.

When I explain it as a technique for problem solving I give one riddle as an example, because at least for me and everyone I have talked to this riddle is so complicated to answer that you need to simplify it using recursion.

Maybe you already know it, some people consider it the most difficult riddle there is.

On an island there are 100 people, each with blue eyes. On this island there is the rule that anyone who finds out that they have blue eyes must leave on the next ferry (there's one ferry per day), so each of the 100 inhabitants doesn't know their eye color. Given that they see 99 people with blue eyes everyone must assume that they might be the only one with a different eye color. Since you don't speak about eye color on that island the situation stays like that.

Now there is a guest on the island, and since he enjoyed his stay he makes a speech when he is about to leave, and as a joke he thought that he gave them a "hint" that contains only information that they already know, so he tells them that there is at least one person with blue eyes on the island.

The riddle is: What happens next?

Now as I said the only way I can argue about an answer is by using recursion, because for recursion you need two things: a trivial case and a way to deduce a more complicated case from the trivial case.

In this riddle the trivial case would be if there was only one person living on the islane. In that case when they were told that there was at least one person with blue eyes it would have to be that one person and they would leave the island on the next ferry.

The way to deduce fron the simple case to a more complex one is to look at the situation with two people on the island, because each of the two persons is observing one person, so each is looking at the trivial case. In the situation with two people there are two possible outcomes: if one of the two has non-blue eyes then the other person is performing the trivial case, because it doesn't matter whether they are the only person on the island or if there are other persons without blue eyes. Persons without blue eyes change the trivial case as much as stones or trees. One of the two persons will see that there is no person with blue eyes in sight and will have to deduce that they are the one person with blue eyes.

But if the second person also has blue eyes the first person will NOT leave the island on the next ferry. That can only mean that they were seeing a person with blue eyes (otherwise they would have had to behave like the trivial case), so when there are two people with blue eyes they both observe that the other one is not leaving on the next ferry and they are both leaving on the second ferry.

Once you have understood that you can extrapolate to 100 people who will have to leave after 100 days when they observe that no one left after 99 days.

It usually takes quite a while until everyone accepts the solution, but I have received good feedback by many students who agreed that it convinced them that there are cases where recursion makes them able to solve a problem that otherwise they couldn't.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is an excellent answer to a question that I did not ask. Why don't you ask that question and use this answer? (It's okay to answer your own question.) $\endgroup$
    – Ellen Spertus
    Jul 6, 2017 at 14:11
0
$\begingroup$

Recursion is sometimes difficult for students to grasp. It's important to understand the concept before implementing it in any programming language. My college professor said that recursion may not make sense today, next week, or next year. But one day it will come to you, maybe when you least expect it. I show this image to help students think recursively. Next, I'll start with a simple recursive program to calculate the factorial of a number. In class, I simulate recursive calls with pieces of paper. I start by writing fact(10) = 10 * fact(9) on a piece of paper. Then I write fact(9) on a new piece of paper and pass it to a student. The student adds to it by writing fact(9) = 9 * fact(8), writes fact(8) on a new piece of paper, and passes it to another student. This process continues until a student must calculate fact(1), which is simply 1. Then all the papers bubble back up to me, and I calculate the final answer. But even with these relatively simple examples, sometimes it takes time to understand recursion. More simple examples help.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It seems as though this doesn't actually address the question asked: "Can anyone recommend a free online source where she can pick up, and ideally practice, recursion?". Could you add some resource from which a student can learn recursion, as the question states? $\endgroup$
    – ItamarG3
    Jul 5, 2017 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.