Entry
Recursion: What is a definition of recursion?
Jan 1st, 2005 11:09
Knud van Eeden,
----------------------------------------------------------------------
--- Knud van Eeden --- 01 January 2005 - 05:53 pm --------------------
Recursion: What is a definition of recursion?
---
In programming, recursion is the possibility of a subroutine or program
module to call itself.
---
It is helpful for writing routines that solve problems by repeatedly
processing the output of the same process.
---
It comes e.g. handy when you have to handle similar looking 'nested' or
hierarchical structures or processes.
---
The structure of your recursive subroutine will look something like
this:
procedure YourProcedureName( YourParameter )
...
IF ... THEN return
...
YourProcedureName( AnotherParameter )
...
end
---
So you see here that this subroutine calls itself
(but usually with another parameter value):
You see the name of the procedure (=YourProcedureName) occurring again
in its body (=YourProcedureName), so it calls itself.
What happens at that moment is that all current values of the local
variables are stored (on a stack), and its last position (=linenumber)
in the subroutine (these are stored on a stack), and the subroutine is
called and processed again with the new parameters.
This will continue until it is informed to stop (that is, when the
'IF ... then return'
statement becomes true).
It then goes backs to the linenumber position after the last state,
restores the variables of that moment and continues from there.
---
e.g.
You want to analyze (parse) a HTML program.
An HTML tag contains tags in tags in tags ...
Thus HTML contains nested tags.
Thus recursion might come handy to analyze this.
(e.g. you start with the tag <HTML>,
which contains the tag <BODY>,
which contains the tag <SCRIPT>,
...
and so on.
Thus tags in tags in tags, ...
So to analyze it, you might write a subroutine with
as parameters the name of the begintag (e.g. 'body').
If you encounter a new begintag, you call your subroutine
again with this new begintag as parameter.
If you encounter an endtag, you return from your subroutine.
In between you do something with the found information.
---
---
Also an XML tag contains tags in tags in tags ...,
thus can be handled similarly.
---
---
Note:
The ability to use recursion should be built in in the programming
language (e.g. C++, Java, Delphi, TSE, ..., but almost all do),
otherwise you have to write the handling of recursion yourself (using a
stack for your parameters and last point of return).
---
---
Book: see also:
---
[book: Mcgregor, Jim (James J.) / Watt, Alan H. - advanced programming
techniques for the BBC micro - Addison-Wesley - 1983 - 376 pages -
ISBN 0-201-14059-4]
---
[book: Rohl, Jeff S. - recursion via Pascal - Cambridge university
press - 1984 - 192 pages - ISBN 0-521-26934-2]
---
---
Internet: see also:
---
Search engine: Google: Recursion
http://www.google.com/search?hl=en&lr=&ie=ISO-8859-1&q=recursion
---
Datastructure: Stack: What is a stack?
http://www.faqts.com/knowledge_base/view.phtml/aid/32760/fid/1279
---
TSE: Programming: Recursion: Link: Overview: Can you give me an
overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/33130/fid/1738
----------------------------------------------------------------------
