8 ms·

Understanding Recursion as an Absolute Beginner

• js2 7y ago
  countDownFrom(--n) There's no reason to reassign the decremented n within the function. Prefer: countDownFrom(n - 1)
  • ChristianBundy 7y ago
    Thank you! This immediately stood out to me as a clever hack that makes it more complicated than it needs to be. I'd have written this function as: function countDownFrom(n) { console.log(n) if (n > 0) { countDownFrom(n - 1) } } This removes both the decrement operator and the return keyword, both of which distract from the concept being taught. This would also make it simple to add a `step` argument, which could be written as: function countDownFrom (n, step) { console.log(n) if (n > 0) { countDownFrom(n - step, step) } }
    • kazinator 7y ago
      coutDownfrom(n--) contains a pointless assignment to a variable that has no use in the function after the logging call. It's not what I'd call clever. It spoils the teaching value of the solution, because a beginner might be confused into thinking that the mutation of n is essential, like that there is only a single n and it is being stepped to bring about the countdown. The student needs to understand that the countdown occurs even though there are no assignments to n, nor anything imperative other than the side effect of the logging call. Don't write beginner examples which contain red herrings that must be explained away to some of the beginners.
      • Fishkins 7y ago
        countDownfrom(n--) produces infinite recursion, which is arguably why you could call coutDownfrom(--n) clever (you have to understand the subtleties of those operators). I agree that "pointless" or "stupid" are better descriptors, though :)
    • rileytg 7y ago
      the only problem with this approach is it doesn’t clearly teach the concept of a base case and a recursive case
      • dev_prashaant 7y ago
        Exactly. That is what I wanted to cover in the blog as well. I could give a better or a difficult example too but that would make it overly complicated which I didn't want it to be.
• diminoten 7y ago
  How "absolute beginner" are we talking here? At what point have we distilled a concept to its bare minimum and failure to understand simply requires the person to spend more time with the concept? If recursion is difficult to grasp, I'm afraid it's not going to get any easier from there.
  • mark-r 7y ago
    Recursion is not something you do very often, so it might just be a matter of having a "aha moment" where you finally get it.
  • dev_prashaant 7y ago
    I have clearly mentioned that if you can declare and call function in the language you are using then you're good enough to go through the blog. That answers your "How absolute beginner" question. The reason why I wrote it is because of my own personal experience. In my programming class, my friends were having hard time understanding recursion so that was the primary motivation for writing this blog.
  • DonaldPShimoda 7y ago
    > If recursion is difficult to grasp, I'm afraid it's not going to get any easier from there. I strongly disagree. Many people have never had to reason about recursion so explicitly before going into CS. Just because it's difficult to understand explicitly at first doesn't mean they won't get better. If they never understand recursion, then that's a problem, but I think that probably says more about the teacher than the student.
    • diminoten 7y ago
      What do you strongly disagree with, exactly?
• vinceguidry 7y ago
  A better resource is How To Design Programs. A better title for it would be "How to design recursive algorithms using Scheme". https://htdp.org/ https://htdp.org/ Every now and again, you need recursion. It doesn't come up too often, simple maps and the occasional reduce handle 95% of tasks. But every once in awhile simple iteration isn't good enough, and you'll be glad you'd gone through HtDP all those years back like I did.
• deleted 7y ago
  [deleted]
• kazinator 7y ago
  Recursion is absolutely easier to understand, period. A big reason for using it is that it's easier to convince ourselves that a recursive solution is correct; it directly gives us the pieces that we need for inductive reasoning. The degree to which a module of code is hard to understand is directly related to the effort required to convince ourselves that it does exactly what it is supposed to, in all cases. Recursive solutions are hard to come up with for someone whose perspective is biased due to having a background in writing imperative code with iteration. They have already forgotten the difficulties they overcame in acquiring their existing skills. Someone who learned nothing but recursion (and pure functional programming) will likely struggle with loops, gotos and assignments.
• tempsy 7y ago
  I like the dark movie theater analogy for beginners e.g. in a dark theater, how would you know what row you're sitting in? You'd ask the row in front of you "what row are you in?" and they'd shake their head and ask the row in front of them and so on until they finally get to the first row, who would know they're in the first row, and at which point they can answer the second row's question all the way back to the row that originally asked the question.
• RcouF1uZ4gsC 7y ago
  >Most of the people find recursion difficult but it's not. Recursion is really hard. According to https://phys.org/news/2019-08-recursive-language-modern-simultaneously-years.html https://phys.org/news/2019-08-recursive-language-modern-simu... Recursive language is a relatively recent phenomenon and even now is much harder to acquire than language and grammar. Recursion is probably the biggest thing that separates our communication from that of other species and gives such a big advantage. That being said, if you are reading HN, you have already mastered a recursive human language. You have the ability to understand recursion. Just be aware that it is one of the more complicated things your brain does, and be patient with yourself. Keep working at it, and eventually you will get it. Don't become discouraged by the process and give up.
  • o_p 7y ago
    Everyone already understands recursion, they just dont know it. If you learned to count, you learned recursion.
  • tempguy9999 7y ago
    While recursive human language and recursion in computing terms are related, I really don't see they gain much from each other. > Recursive language is a relatively recent phenomenon Is there any evidence it's more recent than non-recursive language acquisition, evolutionarily (rather than developmentally ie child to adult)? For reference for others in this thread, an example of linguistic recursion is <https://en.wikipedia.org https://en.wikipedia.org /wiki/This_Is_the_House_That_Jack_Built> This is the horse and the hound and the horn That belonged to the farmer sowing his corn That kept the rooster that crowed in the morn That woke the judge all shaven and shorn That married the man all tattered and torn That kissed the maiden all forlorn That milked the cow with the crumpled horn That tossed the dog that worried the cat That killed the rat that ate the malt That lay in the house that Jack built.
  • justinv 7y ago
    Thanks for sharing this article!
  • ErotemeObelus 7y ago
• pretendscholar 7y ago
  Is there a good example of a time where recursion would be much more efficient than iteration?
  • ur-whale 7y ago
    When thinking about hard problems, recursion is often much more efficient than iteration.
  • saagarjha 7y ago
    Recursion is efficient in developer time: it saves you from having to keep track of context yourself because you can just stick it on the call stack.
  • Merad 7y ago
    I'm doubtful that recursion would ever be more performant than iteration. Iteration with a stack gives you all the capability of recursion without the function call overhead. As others have said, the main advantage of recursion is ease of designing and understanding the solution.
  • rileytg 7y ago
    not necessarily efficient but here’s my latest use case: scheduling a health check job recursively. if the health check fails, it schedules itself to run again in X seconds with N-1 runs until giving up and marking the service as down. iteration here simply wouldn’t work
    • bananasbandanas 7y ago
      Why not? Just schedule a single health check with a loop that tries to health-check N times in a loop, with a delay in between. If the check succeeds at any point, return 'healthy' early. Or schedule N health checks at different times, if any check succeeds cancel all others, etc. etc.
  • SwiftyBug 7y ago
    I like to use recursion when I can't predict the number of iterations necessary to do the job. For example, a program that calculates the total size of a folder. With recursion I can easily iterate through all levels of the tree and get their sizes. I've used the same approach recently when I wrote a GraphQL query generator in Swift. I recursively iterate through an array of dictionaries, each being able to also hold an array of dictionaries of it's own, each being able to also hold an array of dictionaries of it's own, and so on. In the end all I end up with is single a string. Maybe it's not exactly more efficient, but it was certainly much easier for me.
• polygotdomain 7y ago
  I think recursion is very much about finding the right application to learn it, rather than trying to shoehorn an example that doesn't wind up needing a recursive solution. I wound up needing to learn recursion very early on in my programming journey because the problem space I was working in at the time (3D computer graphics) needed it. I found it relatively easy to reason about recursion because the solutions became simpler, more efficient, and more effective when they were solved recursively. Finding those problems that clearly need recursion, are simple enough to grasp, and make good sense are hard, not recursion itself. The variety of contexts that beginners have and the gravitation of computer science to tree traversals as a standard example (or a contrived one like this) is why I think so many get tripped up on recursion when it's introduced.
• arc33 7y ago
  I think the simplest way to understand recursion is as a for loop where you use the stack as the counter. Recursion is basically implementing the operations of a repetitive loop but the loop controls are not explicit like in a for loop, instead you use the stack as the counter of the loop. Once you think of recursion as just another way to do for loops, it immediately is demystified.
  • zwkrt 7y ago
    I don't know if I would consider this easy for a beginner, but it does lead to an interesting result in the 'contrapositive' case: Any recursive solution can be turned into an iterative solution if you store the arguments of the recursive function in a data structure on the heap, and turn the recursive call itself into an access/modification of the data structure. As a specific example, any tail-recursive function can be turned into a for loop that modifies a stack. Recursive functions that are not tail-recursive (such as fibonacci) will require more complex data structures, depending on their internal recursive structure. (fibonacci can use an indexable list, for instance). This is the heart of memoization and dynamic programming.
  • deleted 7y ago
    [deleted]
  • DonaldPShimoda 7y ago
    > Once you think of recursion as just another way to do for loops, it immediately is demystified. I actually think this is not a good way to understand recursion. It's like saying "once you think of the lambda calculus as another way to build a Turing machine, it immediately is demystified." Yes, it's true that they're equally powerful, but their differences are what make one or the other more suitable to certain circumstances. I think with recursion the best way to show this distinction is to look at navigation over a recursive structure, like a binary tree. You could implement any navigation over a binary tree with some nice loops, but they don't really mean anything in relation to the program: they're just a procedure to get the job done. On the other hand, since binary trees are recursively defined (each node is either a leaf containing data or a branch containing two binary trees), using structural recursion to navigate the tree is significantly more straightforward than any looping construct. This is made super clear in a language like Haskell: data BTree = Leaf Int | Branch Int BTree BTree sumTree :: BTree -> Int sumTree (Leaf v) = v sumTree (Branch v l r) = v + (sumTree l) + (sumTree r) But in, say, Python: @dataclass class BTree: pass @dataclass class Leaf(BTree): v: int @dataclass class Branch(BTree): v: int l: BTree r: BTree def sum_tree(t: BTree) -> int: stack = [t] total = 0 while stack: curr = stack.pop() if isinstance(curr, Leaf): total += curr.v elif isinstance(curr, Branch): total += curr.v stack.append(curr.l) stack.append(curr.r) else: raise RuntimeError("Invalid BTree subclass.) return total The Python solution isn't obviously correct. You'll have to read through that and make sure I implemented my traversal correctly — assuming you know what an iterative traversal looks like and you can recognize it without reading the code more fully first. In contrast, the Haskell solution is clearly correct at a glance, I think. Ignoring the difference in length of code, the Haskell is clearly recursing over the structure of the tree. This is, in my opinion, significantly easier to reason about than any amount of looping. I guess the caveat to all this is: recursion is well-suited for certain kinds of problems (such as navigating a recursive datatype), and loops are well-suited for different kinds of problems. But saying "they're equivalent so think of all recursion as loops" is missing the forest for the trees, I think.
• saagarjha 7y ago
  > To do that we can simply return without returning anything i.e. null. I'm no JavaScript expert, but a function that returns nothing results in undefined, no?
  • gridlockd 7y ago
    Indeed, null!==undefined and if you want to return null you must return null. However, null==undefined so you might not even notice the difference.
  • dev_prashaant 7y ago
    Yeah, true. Thanks.
• chiefalchemist 7y ago
  I like recursion; about the same as I like regex. In theory, it feels simple, and the power relative to that is amazing. In practice, it can be aggravating, but once solve it feels so damn good :)
• deleted 7y ago
  [deleted]
• lhnz 7y ago
  When I was a beginner the two problems I had with recursion were: 1. Not handling the base case and accidentally causing an infinite loop. 2. Never reaching the base case so ending up in an infiniite loop. 3. Creating too much incorrect state, and not having a sane way of debugging or visualising this due to the speed and quantity in which it is created. Nowadays, I carefully focus on the first two problems, before moving on to working out a way of visualising the next N function calls, etc.
  • DonaldPShimoda 7y ago
    The way I explain implementing recursion is this: 1. Write down what your function does in a comment. (e.g., "sum all the elements of a binary tree"). 2. Write the function signature. 3. Write the base case. (This is usually straightforward and most people don't seem to have an issue with it when reminded.) 4. Stop thinking. 5. Assume your function already works and write the recursive case. 6. Profit! I find where most people get confused over recursion is in trying to reason about the recursive case. They think "Well if I start at the root of the tree, then the next thing I need is to get the children... and then... with the first child... uh..." They get lost in the recursion. So I tell them: assume your function already works. Trust that you will write it correctly eventually. What does your function do? How can you use that? If you assume you already have a function that sums binary trees, and if you're trying to sum the children of a branch node, well then use that function that you already have to get the sum of each of those children trees, and add up the results! I always recommend to never try to visualize N levels of recursion, unless you're working through an example to actually test your implementation. Worrying about the deeper recursion is how people get lost and confused. Keep it simple: just look at the one layer and assume the other layers will do their job correctly.
• deleted 7y ago
  [deleted]
• cr0sh 7y ago
  I'm not sure when I learned recursion, so I don't know if I can say whether or not I had any trouble with understanding it. I do know that once you understand recursion, knowing how to properly change a routine to a stack or other non-recursive routine (generally because you keep blowing the return call stack because the nesting level gets too deep) can be tortuous at times depending on what the routine is doing. So perhaps that might be an insight to how people facing recursion as a beginner might feel...?
• rvn1045 7y ago
  It’s way easier as a beginner to understand recursion in lisp imo. You can just substitute in all the calls and see the whole structure of the recursive function.
• vchak1 7y ago
  "To understand recursion, you must first understand recursion", said Benoit B. Mandelbrot. When asked about his middle initial he said: it stands for "Benoit B. Mandelbrot".
• 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 ago
    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.
    • alejohausner 7y ago
      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.
  • wittenator 7y ago
    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".
    • alejohausner 7y ago
      Fair enough. I should have said "is most appropriate" rather than "must be used".
  • joelfolksy 7y ago
    The natural solution would be to teach it before loops, yes?
• freetonik 7y ago
  I had good results with my students with the illustrated video explanation I made [1]. It thinks of running functions as boxes that produce output, and of function definitions as box blueprints. [1] https://www.youtube.com/watch?v=vLhHyGTkjCs https://www.youtube.com/watch?v=vLhHyGTkjCs
• VladimirGolovin 7y ago
  To anyone trying to understand recursion, I advice to learn basic Haskell. This is the language where recursion actually "clicked" for me. All you need is very basic Haskell. You don't need functors, applicatives or monads. You only need simple functions, pattern matching, and maybe some parametric polymorphism to simplify the examples and make them more general: fliplist :: [a] -> [a] fliplist [] = [] fliplist (x:xs) = fliplist xs ++ [x] l = [1,2,3,4,5,6,7] f = fliplist l main = print f
• fortran77 7y ago
  Relevant: https://news.ycombinator.com/item?id=20888923 https://news.ycombinator.com/item?id=20888923