Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #5812

Recursion in Computer Science

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Recursion in Computer Science rusi <rustompmody@gmail.com> - 2011-05-19 22:05 -0700
  Re: Recursion in Computer Science Chris Angelico <rosuav@gmail.com> - 2011-05-20 15:18 +1000
    Re: Recursion in Computer Science rusi <rustompmody@gmail.com> - 2011-05-19 22:22 -0700

csiph-web