Can't understand this recursion

Getting Help
1

I have this function as part of a sort functionality, but It just doesn’t make sense to me. Sorry for being so basic.

func appendValues(values []int, t *tree) []int {
	if t != nil {
		values = appendValues(values, t.left)
		values = append(values, t.value)
		values = appendValues(values, t.right)
	}
	return values
}

At the third line it calls appendValues again, which is recursion as far as I know, so I don’t understand how lines 4 and 5 even run?
Doesn’t it all start all over again at line 3?
The full code is here - https://github.com/adonovan/gopl.io/blob/master/ch4/treesort/sort.go

2

Lines 4 and 5 will run after line 3 returns.

Recursive functions don’t “start over”, they call themselves. These function calls work the same as any other function call. The first thing I try to figure out with a recursive function is how it decides to not call itself anymore. In this case it will stop when some t is nil, which is when the end of a branch of the tree is encountered.

1 Like
3

Thank you, that makes sense now.

4

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.