Tuesday, 13 November 2007

Recursive Thinking

I have just woken from a dream where recursion played a part in what happened. In my dream I was in my bedroom and on the phone to a friend, but with two other friends beside me. When one of the friends near me started to sing a Metallica song the other one started to do some of the drumming to the song and my friend on the phone heard this and joined in. It was quite a funny thing. Then I wake from that dream - but I am still asleep in reality, but do not know this - and I'm walking up a hill with one of the friends from my dream, explaining to him about this dream I have had and how funny it was that he could hear the craziness on the other end of the phone and had joined in.

A dream within a dream, a window to another conscious reality constructed by the brain, a dimension within a dimension - recursion. This is not the first time I have experienced a dream of this type but it is pretty unusual and provides an insight into how our minds may actually work.

I was reading recently in New Scientist that recursive awareness may be what separates man from beast. Recursion in thought explains our ability to put ourselves in the position of others (often known as empathy) and understand their point of view on another situation as well as our own. Often at the same time as our own point of view. In fact, we can simultaneously hold our own point of view and view it as others may do and this can affect how we behave. For example, we may not wish to say what we really think as others around us may be offended, even though our point of view is perfectly valid and logical. This, the argument goes, is a uniquely human proposition.

Recursion occurs in daily life too, through the use of grammar. For example, the idea that I'm looking at you, who is looking at me is a recursive statement. It could go further (indeed forever): I'm looking at you, who is looking at me, who is looking at you, who is looking at me... and yet the meaning is clear. Our brains can decipher such complex statements with ease. Another example of it occurring within language is "she said this about her mother who knows that your father is an alcoholic." We really have no problem understanding such a complex piece of information because of our ability to handle recursive concepts in our heads. Maybe it is the secret to intelligence in the brain; that if you can represent a piece of information through recursion you will have a very powerful information processing tool. I will think on this some more as it is entirely relevant to my day to day activities as a developer.

Food for thought. Food for recursive thought.


Zeroth said...

Interesting post. A very good way of explaining recursion to people new to programming. Recursion is usually a very hard to grasp topic, mostly because of the awkward terminology used. Rather, lack of terminology. I have yet to find a good way to represent a recursive chain of logic, or a process in a standard way.

The best so far is the ladder diagram, used for actual inputs. But for more complex recursive algorithms(like in Lisp), then it falls short.

The Recursion King said...

I'm not familiar with ladder diagrams, do you have a quick example I could take a look at?

I find generally that people tend to think of recursion more in terms of straight repetition, even other developers I know. However, when I use recursion to say, parse an XML tree with an unknown number of elements in it at any level (and an unknown number of levels), say, to convert the data to an internal series of hash tables for convenience within a program, I have a mental image of how the process works, kind of like light racing down branches of the tree as they are traversed by the code. Repetition certainly doesn't begin to cover the change in thinking that occurs when programming recursively.

Zeroth said...

The ladder diagram came about when I was trying to help a classmate with recursion in scheme.

For the sum function, it would be like this:

return 1;

Kind of like that, and then you show the returned results as links going back up the ladder.

The tree kind of works as well, but most recursion examples are so trivial that recursion seems more like a toy than a valid tool. To new programmers at least.

The Recursion King said...

That is really good, a way to represent a linear loop as a simple recursive function with an example that is easy to follow for people who do not understand.

Speaking of developers not really getting recursion at first, it always seems to be tied to the exit condition (in my experience). Questions such as "but how will it know when to terminate" and such.

A bit more on topic to my original post though, I'm thinking about making a post about semantic data linking which would be connected to this; recursion would be used to put the "information" back together from its constituent data parts. That could form the basis of an AI system that would, to some degree, emulate how our own brains work.

Zeroth said...

Hmm, but then again, we still don't really have a very good idea how our own brains work. Unfortunately, from what I understand, we know how neurons work, and we know how large structures of the brain work, and what they do. However, we don't understand the middle stages.

Its like understanding electronic gates, and the instruction set of a modern cpu, but not understanding the functional elements that make up the cpu, and how those elements work.

I'd be interested to see where you end up going with the semantic linking though.

The Recursion King said...

Yep this is very true, we do not know any of this for sure, really.

What we do have, though, are clues as to how these processes might work, clues provided by scientific study, our own experiences and by intuition.

I've posted up my thoughts on what I consider to be a structure that resembles how we ourselves learn on the newest blog entry, I'll be interested in your thoughts on this. Whether this is how we really learn is of course up for debate (semantic, connected concepts for representing complicated chains of information may not really be how we work, but there are pointers that suggest it may be).