81–90 of 111 posts
Am I along in never being "taught" recursion? I mean, throughout my curriculum, I've used recursion many times and dealt with everything from fibonacci to quicksort, but never once have I sat through even part of a lecture on "Recursion". Among my peers, I don't think anyone really has an issue with recursion or how it works. Harder to debug possibly, but everyone "gets" it, I feel.
Earlier quoted context omitted.
Agreed - the problem is not recursion, but that it becomes useful for actual complex problems. I understand recursion pretty well at a conceptual level (my background is math, mostly self-taught for CS), but I have a hard time using it for programming. Sure, fibonacci or quicksort are simple, but tree recursion or application to string processing (e.g. for edit distance compuation) is quite harder.
I am the only one who gets upset when fibonacci sequence calculation is used as an example of recursion? Are there other possible examples which are simpler than quicksort, but actually make sense if done with recursion instead of simple loop?
I would consider quicksort to be a quite simple example if you use a high level language. But search in binary search tree and similar tree/graph traversal are maybe better examples, in the sense that most people would find recursion to be more natural than any iterative solution.
Earlier quoted context omitted.
That's certainly a way of representing it. But surely it's equivalent in practice (as long as the next step can't be a nested flight of stairs) to the iterative approach: while there are stairs in front of me climb one stair I guess it's just not as clear to me as it is to you that the "up" utterance is associated with the "climb the stairs" procedure rather than the "climb one stair" procedure.
I agree that it's equivalent in practice; both programs could compile to the same machine code. Where it's different is the human thinking represented by the two programs. The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. It's a conceptually simpler program, up until the point we use that fancy mathematical r-word to descri…
It seems to me that "climb one stair as long as there are stairs" is a conceptually simpler definition than "climb one stair and then climb the stairs if there are still stairs."
I think my point still is I don't see how you're differentiating between these procedures in your daughter's mind— why you're assuming that "up" means "I need to climb all of these stairs" rather than "I need to climb this one stair in front of me."
(If indeed it makes sense to model human behavior either way at all; it probably makes the most sense to think of it more as an event loop...)
Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition. That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a g…
I've been hearing experienced programmers opine for a long time that while is the more natural representation of repetitive tasks. Twelve years ago my oldest was learning to walk upstairs. I watched her say "up", go up one stair, then say "up" again, and go up the next stair. This concrete example of recursively calling the "up" function did more to convince me that recursion is natural than any explanation with abst…
So if your kid was thinking recursively, the last "up" operation would be part of the first "up" operation and also part of every intervening "up" operation. If you asked your kid on the last step of a twelve-step staircase how many "up" she was doing, she presumably wouldn't answer "twelve;" she would answer "one." Would that be because she performed the obvious optimization of a tail-recursive function, or because she wasn't actually thinking recursively?
When learning recursion, there aren't much practice problems people do in imperative languages. Most of the imperative languages don't have tail call optimization and the prevalent culture is to use iteration. That said, there are some problems for which the iterative solution won't be straight forward viz. quicksort, mergesort, binary tree traversal etc etc. But the issue is when a student not very familiar with rec…
When I was writing Ansi Common Lisp I spent a while thinking about why students find recursion a difficult concept. I decided it was because they think of a function as a machine for doing something. E.g. the length function as a machine that finds the lengths of lists. If you think of a function instead as a definition-- e.g. as the definition of length-- then suddenly it's not difficult anymore. At least, that was…
Earlier quoted context omitted.
That's certainly a way of representing it. But surely it's equivalent in practice (as long as the next step can't be a nested flight of stairs) to the iterative approach: while there are stairs in front of me climb one stair I guess it's just not as clear to me as it is to you that the "up" utterance is associated with the "climb the stairs" procedure rather than the "climb one stair" procedure.
I agree that it's equivalent in practice; both programs could compile to the same machine code. Where it's different is the human thinking represented by the two programs. The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. It's a conceptually simpler program, up until the point we use that fancy mathematical r-word to descri…
I disagree. The word "while" does connote time, but it's just the word chosen by early programmers to describe a process of performing an action immediately depending on current conditions, with no knowledge of history. Recursion amounts to the same thing -- after you make the mental leap of a tail-recursive optimization. When you climb the next step, you're climbing it because it's part of the definition of climbing the rest of the steps, which was part of the definition of climbing the rest of the steps when you were on the previous step. As I pointed out in another comment, when you're climbing the last step of a twelve-step staircase, you're actually performing twelve "climb up the steps" operations that are nested like Russian dolls. Thinking recursively is only simple when you learn to mentally simplify all of that, basically to think in terms of the "same machine code" you mention in your comment. I don't think we arrive at that "machine code" starting from a recursive definition of climbing the stairs. It seems much more likely that we figure out the implementation (the while loop) long before we figure out (if we ever do) that we can derive that implementation from a recursive definition of the task.
Earlier quoted context omitted.
Why, though, do they think of a function as a machine for doing something? Because we tell them so. Before starting any standard CS curriculum (ignoring, for a moment, self-taught hackers), the only place a student should have heard about "functions" is in math class---where they are definitions. They get to intro Java and we tell them "no, no, that's not a function, this is a function, look, it's got variables and f…
Your "methods" have also been called "procedures".
When learning recursion, there aren't much practice problems people do in imperative languages. Most of the imperative languages don't have tail call optimization and the prevalent culture is to use iteration. That said, there are some problems for which the iterative solution won't be straight forward viz. quicksort, mergesort, binary tree traversal etc etc. But the issue is when a student not very familiar with rec…
Earlier quoted context omitted.
Any "divide and conquer" algorithm is likely to be recursive. Thus, for instance, the FFT, the Karatsuba multiplication algorithm for large integers, Strassen's matrix multiplication algorithm for matrices and the like are all recursive. Moving on, dynamic programming is a very important technique. About half the time it is easier for me to figure out a dp solution by writing a recursive solution with memoization tha…
You can talk about "divide and conquer" but the most common problem where recursion really helps is looking at tree data structures. As then to consider looking for the total of some value stored in an XML tree. In an iterative language it's a for loop and then calling the function on each of the children. In a Lisp it's calling it's self on the child and next node. PS: Showing someone they can transform a recursion…