5 ms·

I often fail recursion questions during interviews because I don't like thinking about recursion. It's too stupid and pointless to think about.

ludamad 11y ago
Even when working with trees?
- a3voices 11y ago
  Why would you ever work on the internals of how trees work? That has 0 business value 99.99% of the time. It's all solved problems. And even so recursion might not be the best approach.
  - barrkel 11y ago
    If you ever develop any abstraction over the raw DOM when writing a rich web app, you'll be dealing with trees, and if your abstraction supports nesting, you'll be dealing with recursion.
    - douche 11y ago
      Because we don't have enough new JavaScript front-end frameworks coming out every week.
  - baddox 11y ago
    Trees don't always call themselves "trees." They can sneak up on you. Nested lists, for instance, are equivalent to trees, and nested lists show up all the time. Perhaps your programming languages has some sort of recursive map function builtin, but a lot of common languages don't, and it really helps to be able to intuitively think about recursive traversal.
  - akamel 11y ago
    when did the dumbing down of programming start? I'm all for code-reuse and componentization but common... recursion is programming 101!
    - jharger 11y ago
      Well, I imagine if your background/education wasn't computer science, and you didn't have an intro to algorithms and data structures, (and also not that into math) recursion would feel unnatural and strange. I say this because I was originally a self-taught programmer, and I hated recursion too. Once I went to school for a CS degree, I learned how awesome it really was, and now I use it all the damn time.
      - dvt 11y ago
        I studied math and I find recursion unintuitive, whereas I find the Principle of Induction[1] profoundly intuitive (the two are very closely related). [1] https://en.wikipedia.org/wiki/Mathematical_induction https://en.wikipedia.org/wiki/Mathematical_induction
        ScottBurson 11y ago
        So what is it about recursion that eludes you? It is very strange to me that someone would find one of those concepts easy and the other not -- as you say, they are two forms of the same thing.
        dvt 11y ago
        I guess it's more reading and writing it in code. In my case, it makes sense to read code like I read a book: it has a beginning, a middle, and an end. (Procedural, see?) A recursive function makes me do all these convoluted mental gymnastics when I'm just trying to figure out if Cinderella lived happily ever after or not.
        ScottBurson 11y ago
  - com2kid 11y ago
    Have you ever worked on a UI? Ever? Those are trees. Want to walk the UI to find an element? Trees. Want to manipulate the DOM? Trees. Walk a file system? Write a file system? Trees and trees.
  - Osmose 11y ago
    I once worked on a website that analyzed Python code in order to index it into elasticsearch for structural search queries (things like "find me all classes that inherit from SomeBaseClass"). Python's built-in ast library outputs a tree for you to traverse, and even with their provided tree walker you still deal with the internals of the tree and recursion. Furthermore, part of our indexing needed to follow imports to find the canonical name of a value, which is a problem very well suited to a recursive solution. You may not have encountered these situations where recursion and trees have to be dealt with, but they absolutely exist.
  - cscurmudgeon 11y ago
    Well how do you think those got solved in the first place?
lostcolony 11y ago
I use AWS. I want to take my JSON, and store it in Dynamo. I need to convert every object object embedded in my top object to a {"M" : {...}} structure, and every array/list to a {"L" : [...]} structure. So something like - {"a" : {"b" : [1]}} should become {"a" : {"M" : {"b" : {"L" : ["N" : "1"]}}}}. The easiest way to write one function that can handle that in a generic way, no matter how complicated the data structure (barring hitting the stack limit), is recursion.
- jsprogrammer 11y ago
  Eh. I don't think writing a custom stack implementation would be any more difficult and you'd get to scale to the memory of your machine rather than your language's runtime.
  - lostcolony 11y ago
    I'd love to see the code for that if you've got it (I have a recursive version in Javascript). Because the recursive one is really simple to read, intuitively grasp what is going on, confirm is correct, test, modify, etc. And rewriting it to use a stack, while possible, feels harder to me to think up, reason about, and no matter how I try comes out uglier. I haven't spent a lot of time on it, mind you (in part because the recursive one hits everything I care about), but I'd love to see one as elegant written iteratively.

ludamad 11y ago

Even when working with trees?

a3voices 11y ago
Why would you ever work on the internals of how trees work? That has 0 business value 99.99% of the time. It's all solved problems. And even so recursion might not be the best approach.
- barrkel 11y ago
  If you ever develop any abstraction over the raw DOM when writing a rich web app, you'll be dealing with trees, and if your abstraction supports nesting, you'll be dealing with recursion.
  - douche 11y ago
    Because we don't have enough new JavaScript front-end frameworks coming out every week.
- baddox 11y ago
  Trees don't always call themselves "trees." They can sneak up on you. Nested lists, for instance, are equivalent to trees, and nested lists show up all the time. Perhaps your programming languages has some sort of recursive map function builtin, but a lot of common languages don't, and it really helps to be able to intuitively think about recursive traversal.
- akamel 11y ago
  when did the dumbing down of programming start? I'm all for code-reuse and componentization but common... recursion is programming 101!
  - jharger 11y ago
    Well, I imagine if your background/education wasn't computer science, and you didn't have an intro to algorithms and data structures, (and also not that into math) recursion would feel unnatural and strange. I say this because I was originally a self-taught programmer, and I hated recursion too. Once I went to school for a CS degree, I learned how awesome it really was, and now I use it all the damn time.
    - dvt 11y ago
      I studied math and I find recursion unintuitive, whereas I find the Principle of Induction[1] profoundly intuitive (the two are very closely related). [1] https://en.wikipedia.org/wiki/Mathematical_induction https://en.wikipedia.org/wiki/Mathematical_induction
      - ScottBurson 11y ago
        So what is it about recursion that eludes you? It is very strange to me that someone would find one of those concepts easy and the other not -- as you say, they are two forms of the same thing.
        dvt 11y ago
        I guess it's more reading and writing it in code. In my case, it makes sense to read code like I read a book: it has a beginning, a middle, and an end. (Procedural, see?) A recursive function makes me do all these convoluted mental gymnastics when I'm just trying to figure out if Cinderella lived happily ever after or not.
        ScottBurson 11y ago
- com2kid 11y ago
  Have you ever worked on a UI? Ever? Those are trees. Want to walk the UI to find an element? Trees. Want to manipulate the DOM? Trees. Walk a file system? Write a file system? Trees and trees.
- Osmose 11y ago
  I once worked on a website that analyzed Python code in order to index it into elasticsearch for structural search queries (things like "find me all classes that inherit from SomeBaseClass"). Python's built-in ast library outputs a tree for you to traverse, and even with their provided tree walker you still deal with the internals of the tree and recursion. Furthermore, part of our indexing needed to follow imports to find the canonical name of a value, which is a problem very well suited to a recursive solution. You may not have encountered these situations where recursion and trees have to be dealt with, but they absolutely exist.
- cscurmudgeon 11y ago
  Well how do you think those got solved in the first place?

lostcolony 11y ago

I use AWS. I want to take my JSON, and store it in Dynamo. I need to convert every object object embedded in my top object to a {"M" : {...}} structure, and every array/list to a {"L" : [...]} structure. So something like - {"a" : {"b" : [1]}} should become {"a" : {"M" : {"b" : {"L" : ["N" : "1"]}}}}. The easiest way to write one function that can handle that in a generic way, no matter how complicated the data structure (barring hitting the stack limit), is recursion.

jsprogrammer 11y ago
Eh. I don't think writing a custom stack implementation would be any more difficult and you'd get to scale to the memory of your machine rather than your language's runtime.
- lostcolony 11y ago
  I'd love to see the code for that if you've got it (I have a recursive version in Javascript). Because the recursive one is really simple to read, intuitively grasp what is going on, confirm is correct, test, modify, etc. And rewriting it to use a stack, while possible, feels harder to me to think up, reason about, and no matter how I try comes out uglier. I haven't spent a lot of time on it, mind you (in part because the recursive one hits everything I care about), but I'd love to see one as elegant written iteratively.