News for hackers. Stuff that matters.

A comment on Understanding Recursion as an Absolute Beginner.

Re:Understanding Recursion as an Absolute Beginner by alejohausner on Thursday September 05, 2019 @10:52PM (#20892615)
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).

[ Parent | on HN ]
Re:Understanding Recursion as an Absolute Beginner by wittenator on Friday September 06, 2019 @02:14AM (#20893478)
Just 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".
[ Parent | on HN ]
Re:Understanding Recursion as an Absolute Beginner by alejohausner on Friday September 06, 2019 @11:18AM (#20896401)
Fair enough. I should have said "is most appropriate" rather than "must be used".
[ Parent | on HN ]
Re:Understanding Recursion as an Absolute Beginner by physicles on Thursday September 05, 2019 @11:58PM (#20892937)
True. 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.
[ Parent | on HN ]
Re:Understanding Recursion as an Absolute Beginner by alejohausner on Friday September 06, 2019 @11:16AM (#20896387)
True, 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.
[ Parent | on HN ]
Re:Understanding Recursion as an Absolute Beginner by joelfolksy on Friday September 06, 2019 @01:21PM (#20897606)
The natural solution would be to teach it before loops, yes?
[ Parent | on HN ]