On the sixth day

… the creator came up with the recursive function. And he saw that it was good. So good in fact, that his game assets problem were now solved. All he had to do now was pick a point and zoom. Satisfied, he packed his bags and went to the beach.

Wait for it

7 Likes
1 Like

Yes my finger was hovering over the edit button as soon as I posted it. Decided to leave it. But yes I agree, iteration is technically correct

EDIT: nope, I was correct

Recursion in math is not the same thing as recursion in a program.

From wikipedia, definition of recursion:

Other recursively defined mathematical objects
 include factorials, functions
 (e.g., recurrence relations), sets
 (e.g., Cantor ternary set), and fractals.[2]
4 Likes

When you said that, I thought for a moment this was going to be about Perlin noise (and variations thereupon).


I expect @drummyfish is the real authority when it comes to fractals, but hopefully I can clear up a few things about recursion and iteration (and hopefully someone will actually find this interesting)…

That site’s definition breaks down at “Does not uses stack.”.

Iteration doesn’t use a call stack, but that doesn’t mean it can’t use a stack. If you factor in having a stack data structure then iteration can do nearly anything recursion can do.

Even without a stack, any function that is primitive recursive can be implemented both iteratively and recursively.

For example:

void iterative()
{
	for(int i = 0; i < 10; ++i)
		std::cout << i << '\n';
}

void recursive(int i = 0)
{
	if(i < 10)
	{
		std::cout << i << '\n';
		++i;
		recursive(i);
	}
}

(Technically this is corecursion rather than recursion, but the order is important in this example.)

(Edit: I accidentally left out the tail call the first time around. I’ve rectified that now. Hopefully it didn’t cause people too much confusion.)

In fact, there’s a property called tail recursion that allows a compiler to effectively turn a tail-recursive function into an iterative function by replacing the final call with a jump instead. It does this by treating the arguments as variables and modifying them directly rather than starting a new stack frame. At an assembly level, tail recursion can be identified by a ret instruction occurring directly after a call instruction.

For more info about tranforming recursion into iteration, the article here has some decent examples.

Recursion in maths is the same as recursion in programming.

The only real difference is in the colloqial/uninformed usage: many programmers treat ‘recursion’ as being related only to recursive functions, but there’s actually more applications of recursion in programming than just recursive functions.

One other application of recursion in programming is recursive data types

For example, a cons list (a kind of singly linked list) implemented in Haskell:

data List a = Empty | Cons a (List a)

This is recursive because it defines a tagged union/sum type in which one constructor recursively refers to its own definition, thus a cons-list is in fact a recursive data structure. I.e. it is recursive because it contains itself.

Other examples include various tree data structures (which are unfortunately rather neglected outside functional programming):

data RoseTree a = Node a [RoseTree a]
data BinaryTree a = Null | Branch a (BinaryTree a) (BinaryTree a)

(If anyone wants some examples in languages other than Haskell, I can provide some. I picked Haskell simply because the definitions are a lot more terse.)

3 Likes

nope I don’t know too much about them really, just the basics and something about how to render them maybe (as I was studying how Marble Marcher rendered them so nicely in real time)


BTW great point about the recursive data types.

I’d say recursion is simply a definition that uses the term that it is defining (be it a definition of whatever, a function, a type, a word in a language, …). And one way to evaluate any finite recursion is by iteration with stack.

3 Likes