Recursion deals with recursive data structures, and iteration deals with "plain old" data structures.

When you use one to process the other, you get into trouble. For example, you need to manage a stack to do iteration on your binary tree. Or you need to construct slices to recurse on your arrays.

It's all about ergonomics.

▲ pdpi 5 days ago | parent | next [-]

> For example, you need to manage a stack to do iteration on your binary tree

Recursion around trees can get you into trouble with the stack. Consider:

    def traverse(node):
      do_work(node.payload)
      traverse(node.left)
      traverse(node.right)

The second recursive call to traverse is in tail position and is a candidate for elimination, but the first one isn't and will _always_ eat stack space. This is fine if you know what you're doing, but can bite you in the arse if you're expecting TCO to save you.

	▲	javcasas 4 days ago \| parent [-]
		TCO stands for "TAIL call optimization". It will obviously not save your arse if the call is not in the tail of the function, exactly the same as "python generators will not help you if you are doing C++".

▲ eru 5 days ago | parent | prev | next [-]

What's a plain old data structure?

Linked lists are recursive, but you can use loops just fine to deal with them.

Similarly, it depends on what you do with your trees. If you want to go down a single path (eg to find an element in a search tree), loops aren't too bad.

And arrays don't necessarily ask for loops. Eg implementing quicksort or heap sort with loops is possible (and depending on your language, compiler and target machine might have performance benefits), but I'd hardly call it ergonomical.

Despite all my criticism you are hinting at a good point though: it's often useful to define your data structures together with combinators that work on them. So eg you want to define various tree traversals together with your tree. (Most people are familiar with the combinators 'map' and 'filter' for lists but that's a very small pool.)

Whether those combinators are implemented with recursion or loops is an implementation detail that the user of the combinator doesn't need to worry about too much.

▲ dreamcompiler 5 days ago | parent | prev [-]

This is overly simplistic.

Is a binary tree recursive from the perspective of a type declaration? Yes.

Is it recursive from the point of view of search? Depends. If you're doing depth-first search, then you need a stack and a recursive algorithm seems natural. If you're doing breadth-first search, then you need a queue and the algorithm is less obviously recursive.

In either case the program could be expressed recursively or as an explicit loop. When a stack is needed, the underlying hardware always provides automatic stack management so recursion feels natural in that case.

When a queue is needed it's more of a tossup since hardware and programming languages don't generally provide automatic queue management, so you're going to need to manage that data structure manually anyway. In which case whether you choose to use recursion or not is more of a personal preference.

▲

eru 5 days ago | parent | next [-]

> When a stack is needed, the underlying hardware always provides automatic stack management so recursion feels natural in that case.

Not true at all. Eg Risc-V provides no stack management at all. But compilers and interpreters exist, so it doesn't make a difference to how your high level code 'feels'.

▲

javcasas 5 days ago | parent | prev [-]

So a tree is easier to do recursing vs iterating in some cases, whereas in other cases recursion and iteration have roughly the same level of complexity.

Kinda shows that recursive data structures are usually better dealt with recursion. Worst case you end up with the same level of difficulty as iteration.

▲

busterarm 5 days ago | parent [-]

My career is practically built on the fact that other people 99% of the miss the simplest representation of the data/problem.

Just look at myriad ways that people implement something like checking win conditions in Rock, Paper, Scissors. Switch statements, conditional hell, etc.

...you can just do something as simple as stick Rock, Scissors, Paper into a circular list and compare to the next element. It's practically readable as plain English. No programming skill required.

If you need to code golf you can use modulo arithmetic, for a different kind of "simple", but then you lose readability.

▲

eru 5 days ago | parent [-]

You could have a big pattern-match statement for Rock, Scissors, Paper and it would still be readable (in a language that supports these things like eg Rust).

The circular list seems a bit too cute for me. Sure, it's possible, but seems like overkill.

▲

busterarm 5 days ago | parent [-]

If you have to do a bunch of list manipulation yourself sure but most scripting languages make these things trivial.

Heck, you could easily write it using Terraform built-in functions.

	▲	eru 4 days ago \| parent [-]
		What do you mean by 'list' in this case? Python, for example, has a list data structure, but it's different from what C folks would naturally think of when you say 'list'.