Recursion in Computer Science
rusi
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
> On Fri, May 20, 2011 at 3:05 PM, rusi <rustompm...@gmail.com> wrote:
> > - 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
Yes sure Thanks.
An exhaustive list would be much longer (and I got tired of typing)