How would you use recursion in Godot?

This is a READ-ONLY snapshot of the Godot Community Forums when TwistedTwigleg was the owner, which is hosted for archival reasons only. The current Godot Community Forums can be found here.

Some links may point to external websites, including the current Godot Community Forums. These websites are not associated with TwistedTwigleg.

Erich_L

Recursion to me just boils down to calling a function x inside of function x. I was working on my course when I realized boxes inside boxes inside boxes might be a good example of how to use recursion so I figured why not test out my equipment and put a short video together?

I have to admit I am having some trouble thinking of other (better, even?) examples- so I wanted to ask if anyone here has used recursion cleverly in gdscript.

Pixophir

Had a similar question recently concerning gdscript because some things just need a lot of recursion, like building spacial data structures or selecting elements for rendering or physics tests. The clear answer was "Yes, gdscript supports recursion" @cybereality . Haven't tried gdscript yet because am still in C++.

Recursion isn't difficult. Enter the function, first(!) test condition if the end is reached, if yes, return fixed value. If not, return function call with new parameters. Recursion takes place on the stack, so do a short estimation if that's not limiting the thing, or else bust.

Sure you can do any recursion also iteratively, but it is usually a lot more to write (and thus more difficult to maintain). Compilers these days are good ... scrub ... interpreted language. Nevertheless, to recurse is is advisable usually when a problem can be divided such that each sub-problem has the same solution path. Path finding, ray/path tracing, graphs, directory trees, these kind of things.

Classical example you could plug in to check (also the size of the stack ;-)): Fibonaccy

int fibonacci(int n) {
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return (fibonacci(n-1) + fibonacci(n-2));
}

Edit: here you go, took just a few seconds, my first own gdscript not typed from some turoial 🍾

extends Spatial

func fib(n):
	if(n == 0):
		return 0;
	elif(n == 1):
		return 1;
	else:
		return(fib(n-1) + fib(n-2))

func _ready():
	print("fib(10): ", fib(10))

duane

My dungeon room generator used recursion initially, though I rewrote it to use a stack because of recursion's tendency to fill up the system stack. [I try not to encourage people to use straight recursion -- it's not necessary, and it can cause problems.] This was when I was using lua, so there was never a gdscript version.

Originally, it worked something like this.

tree = split_rect(dungeon_sized_rectangle, 8)

function split_rect(rectangle, iteration):
	if iteration > 0:
		rectangle1, rectangle2 = divide_rectangle_in_two_randomly(rectangle)
		return btree_of(
			split_rect(rectangle1, iteration - 1),
			split_rect(rectangle2, iteration - 1)
			)
	else:
		return rectangle

When you read out the list of rectangles from the tree, and shrink them a bit, they make a nice dungeon map worth of rooms.

The corridors are made by connecting every pair of split rectangles, as well as all their pairs of ancestors.

Edit: This is the recursive version (split_rect_recursive in dungeon.gd), but it's way too big for an example.

Pixophir

Looking more closely at the video, I think there's room for improvement, because it is essentially schlepping counter and abort condition with it for every stack frame.

I'd show it like a call with parameters box and count, on enter first(!) compare counter to 0, then recurse with next box and --counter. Thus it is clearer, uses fewer stack space, and also avoids introducing accidental ub by hiding the abort condition in the recursion part. It looks like half recursion, half iteration to me.

Don't know the box class, could even be that createBox could be called directly thus saving one more parameter.

Just my two cents. Maybe I am just stuck in C++ thinking, where I usually don't do things with a hot needle :-)

DaveTheCoder

Since a Godot scene consists of nodes arranged in a tree, which is a recursive data structure, recursion is the natural way of traversing all the nodes in a scene, or all the descendants of a node. For example, if you need to set or view a property, or call a method, on every descendant of a node, it would be natural to use recursion.

Erich_L

DaveTheCoder My Box code turned into a hot mess with each one having an array of contents and a reference to the box it itself is inside of. You made me realize that when I add something to one of the inner boxes my code is actually recursively asking all the outer boxes to recheck their helium amounts, so ... brain working ... just scene tree traveling might be the best/most simple example of recursion- except I don't know if I can visualize it as well as boxes in boxes.
Another reason I think your examples are great is because you might not know in advance how many times that function will be called.. which makes me start thinking again.. is it really true every use of recursion could be replaced with a for loop?
Edit: maybe just use a while(true) and break at the bottom of each tree?

Erich_L

Wow, those are solid places to use recursion. Thanks a lot for sharing those examples. I feel ashamed I mostly put that video together to test my hardware/software recording setup and now I regret not thinking about the code more. I went off to play Dune last night but all I could think about was someone saying recursion can always be replaced with a for loop. I had used recursion in that example because it provided references to the boxes I needed. Then I realized I could just skip recursion and write:

	var box = createBox(0,0,0)
	var innerBox
	for i in range(15):
		innerBox = box.addBoxtoBox()
		box = innerBox

I lost at Dune. Time to remake that video!

DaveTheCoder

If you search for "convert recursion to iteration", there are articles explaining how to do it.

I first learned how when I took a course in college using this textbook:
https://en.wikipedia.org/wiki/Principles_of_Compiler_Design

Kojack

Recursion and iteration are interchangeable, but the effort may not be balanced, depending on the algorithm. Doing something a fixed number of times is easier with a for loop than recursion. Doing octree processing is easier with recursion. In some cases using iteration instead of recursion means basically recreating part of the underlying mechanics (stacks) anyway.

Since Lua was mentioned above, the real interesting case is tail call recursion.
Tail call recursion is a special case of recursion where it doesn't grow the stack. Lua, Kotlin, Haskell and some javascript engines support it. Most other languages don't (or are limited).

For example, in Lua:

function aaa()
	print("aaa")
	bbb()
end
function bbb()
	print("bbb")
	aaa()
end

aaa()

This will run for a little bit, then crash when the stack overflows.

But this version uses tail calls:

function aaa()
	print("aaa")
	return bbb()
end
function bbb()
	print("bbb")
	return aaa()
end

aaa()

When Lua sees you are returning the return result of a function, it overwrites the current stack frame since it knows nothing further is needed from it. That second version can run recursively forever.

GDScript and C# don't support tail calls though, so none of what I've said is really relevant, just interesting. 🙂

Erich_L

I remade that video and it turned out quite a bit shorter, added a helium-based fireworks show at the end. @Kojack It is super interesting, I hadn't heard of tail calls before. I feel really good about using godot to illustrate these concepts visually- still don't feel like this turned out as clear as it could have.

cybereality

Here is an simpler Fibonacci.

func fib(n):
	if n <= 1:
		return n
	return fib(n-1) + fib(n-2)

DaveTheCoder

Here's a function in my project that uses recursion to traverse a branch of the scene tree:

# Set the focus_mode to the specified value for the child Controls of the
# specified node.
#
# Parameters:
#	node - Node whose child Controls are to be changed.
#	mode - enum Control.FocusMode: Control.FOCUS_NONE, Control.FOCUS_CLICK, or
#		Control.FOCUS_ALL.
#	recursive - If true (default), all the descendent Controls are affected.

func set_child_controls_focus_mode(node: Node, mode: int,\
		recursive: bool = true) -> void:
	for child in node.get_children():
		if child is Control:
			child.focus_mode = mode
		if recursive:
			set_child_controls_focus_mode(child, mode)