Recursion in Computer Science


R

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
 
Ad

Advertisements

C

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
 
Ad

Advertisements

R

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)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top