Recursion in Computer Science

[rusi]

There have been a number of unrelated discussions regarding recursion
on this list.
I believe that recursion occurs in a wider spread of areas than is
usually recognised.

Heres a list of some such areas.
Please note I am using recursion in a broad and somewhat fuzzy sense.
Narrow specific definitions would lead to conclusions like:
-- Prolog has no functions or procedures so it has no recursion
-- Since recursion is equivalent to stack + iteration therefore
Fortran supports recursion.

Heres (an initial approx to) such a list:
-------------------------------------------------------

recursive functions
recursive data -- eg linked lists, trees
nesting
self reference -- Y combinator
well founded induction
structural induction
bootstrapping
language to describe language -- syntax
- yacc in yacc
language to describe language -- semantics
- lisp in lisp -- metacircularity
Goedel's theorem <- meta-mathematics <- ordinary math
undecidability <- universal TM <- Turing machine as ordinary computer
reentrancy
[An OS-like program fails to be reentrant for the same reason that
Fortan-like language fails to support recursion -- Non use of stack]
virtualization in OS
Introspection in modern languages
Models to metamodels
corecursion
- laziness, infinite datastructures
- semantics of generators/iterators in python
Von Neuman machine
- code is data -- therefore quondam hardware becomes software
- data can be code -- viruses

 

[Chris Angelico]

 - data can be code -- viruses

It's not JUST viruses. There's plenty of legitimate reasons for your
data to actually be code... that's how compilers work!

Chris Angelico

 

[rusi]

It's not JUST viruses. There's plenty of legitimate reasons for your
data to actually be code... that's how compilers work!

Chris Angelico

Yes sure Thanks.
An exhaustive list would be much longer (and I got tired of typing)