4 ms·
The problem with recursion (and with the counting example in the post) is that a student will ask "why can't I do this with a loop?" It's better to use a probl
by alejohausner 7y ago
The problem with recursion (and with the counting example in the post) is that a student will ask "why can't I do this with a loop?" It's better to use a problem where recursion MUST be used, such as a binary tree:
The size (# of nodes) of a binary tree is:
- 0, if the tree is empty, or
- size of left subtree + size of right subtree + 1
If you draw a tree, any student will agree that the recursive method makes sense. Indeed, they would be hard-pressed to come up with solution that uses a loop (unless they know about stacks, OK OK).
- physicles 7y agoTrue. But then you need to first teach the student about pointers/references, linked lists, and then binary trees. The point of this article was to explain recursion to an absolute beginner.
- alejohausner 7y agoTrue, you need pointers to implement binary trees. But you just need chalk to draw one, and to explain a recursive algorithm that acts on it.
- wittenator 7y agoJust a nitpick, loop languages and recursive languages have the same expressive power. Therefore you can write a loop program for any recursive one. So there is no "must".
- alejohausner 7y agoFair enough. I should have said "is most appropriate" rather than "must be used".
- joelfolksy 7y agoThe natural solution would be to teach it before loops, yes?