Recursion vs loops

Ok, you faggots. Since many of you seem to dislike recursion tell me how you would extract information out of the tree in pic related.
You only get access to the top node. Each node can have any number of subnodes. Create a list that contains all bottom nodes that don't have subnodes of their own.
These are my solutions (pseudo code and not tested, don't bitch). They don't return exactly the same lists, though, as the order of the elements will be different.
I'm a recursion fag so loop code might be shit. I'm also just a hobby programmer so both might be shit.

Recursion
List getBottomNodes(Node parent_node) {

List bottom_nodes;

addBottomNodesToList(parent_node, bottom_nodes);

return bottom_nodes;
}

void addBottomNodesToList(Node node, List bottom_nodes) {

if (node.getChildNodes().size() > 0) {

for (Node child_node: node.getChildNodes()) {

addBottomNodesToList(child_node, bottom_nodes);

}

} else {

bottom_nodes.add(node);

}
}


Loop

List getBottomNodes(Node parent_node) {

List bottom_nodes, List parent_nodes;

parent_nodes.add(parent_node);

while (parent_nodes.size() != 0) {

for(Node child_node: parent_nodes.get(0).getChildNodes()) {

if(child_node.getChildNodes() > 0) {

parent_nodes.add(child_node);

} else {

bottom_nodes.add(child_node);

}
}

parent_nodes.remove(0);
}
}

Attached: BST Example.png (1200x600, 42K)

if(child_node.getChildNodes() > 0) {
should be
if(child_node.getChildNodes().size() > 0) {

Recursions are pretty much only used for trees.
It's only time loops are more confusing that recursion.

in Binary tree, you just
addNode(node->leftNode, value)
addNode(node->rightNode, value)

and here in non binary (no one would ever use that) you need to do it in a for each loop

def get_leafs(root):
leafs = []
queue = [root]
while len(queue) > 0:
node = queue.pop()
for chld in node.children:
if chld.is_leaf(): # len(chld.children) == 0
leafs.append(chld)
else:
queue.append(chld)
return leafs

Every loop construction could be transform to recursive construction.

Every recursive construction could be transform to loop construction.

Usually recursive means use implicit queue recursion in functions over explicit queue in loops.

Recursion queue in function had overload and possible overflow but it’s more elegant, some languages support tall call optimization.

Loops > Recursion

Good job doing OPs homework. Now he can finish high-school.

did you mean a list that contains all leafs of a binary tree?


func noRecursion(Tree root):
List l;
Queue q;
q.enq(root)
while !q.isempty():
Tree t = q.deq()
if(t.dx == null and t.sx == null):
l.add(t.data)
end
if t.dx != null:
q.enq(t.dx)
end
if t.sx != null:
q.enq(t.sx)
end
end
return l
end

If I needed it for homework I would have specified a language.

Yeah. Didn't know the right word. As I said I'm only a hobby fag.

literally same what OP posted just in different lang

Use Lisp.

>Reddit spacing your code

recursion is not magic, you are just using the implicit stack of a procedure. If you explicit an auxiliary structure( a stack or a queue for example) the code is trivial in your simple example

>and here in non binary (no one would ever use that) you need to do it in a for each loop
I use it for a program I'm writing at work. It's for designing PLC programs.
Every signal (input, output, junction) is represented by a node.
For example an output could have a conjunction as subnode which in turn has several inputs as subnodes.
It's just how I structure the data. Could probably also be done in a relational database but I find it much more elegant this way.

Iteration and recursion are interchangeable. If your compiler supports tco, recursive solutions may be easier to write and grok

I don't actually do that. Only did that here so brainlets have it easier to read.

You ought to give us an interface for the Nodes

Don't call other people brainlets when you call yourself a "recursion fag", like it's even a fucking thing. See and

That just means that I prefer recursion and I've seen tons of people here bitch about recursion. So it's seems to be a thing even if it's just about preference.

Recursion is slower

Did you post this looking for approval? This code is available in any Computer Science text book. Not sure what you're looking for.

I licked a negro once.

why not both? Use recursion to explore a tree and its nodes, then store a reference of each node in a new list. Finally, you can iterate through the list.

recursion vs iteration isn't a debate, or a preference
if you need a stack then you use recursion
if you don't then you iterate

>Recursion
*pshht* *crack*
*sip*
Now THAT's a programming technique! Really a shame how kids these days use structured programming shit like loops. Who do they think they are? Hackers or some shit? Back in my days, abstraction was praised for its expressive power. Praise SICP!

Attached: monster boomer.jpg (250x229, 8K)

Iteration is a boomer meme

none of these concepts pre-date the other

Recursion is frowned upon because most languages aren't sophisticated enough fpr tail call optimization.

For looping in a case normally done recursion, just maintain your own stack.

why would i use trees? just use sqlite

boomer memes are a boomer meme

My solution last time I encountered a large tree I used a commandstack on the heap.

I'm not that familiar with functional programming languages, can they help me to diagnose if the recursive function is tail call optimized or do I have to check the generated code manually?

some functional programming languages guarantee tail call optimization in all cases.

sounds like bs to me, you can't tco every recursive function

It's part of the Scheme standard. Of course that only refers to the activation record ("stack frame") and not anything allocated on the heap.

You still can't tail call optimize every recursive function unless it conforms to a specific form; otherwise all languages would do it and no one would have to care about using loops or recursion.

they bitch because if you don't use tail calls and your compiler doesn't optimize them, you're wasting a lot of memory iirc