Xref: utzoo comp.edu:3691 uw.general:1945
Path: utzoo!attcan!uunet!ogicse!dali.cs.montana.edu!milton!Tomobiki-Cho!mrc
From: mrc@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <9882@milton.u.washington.edu>
Date: 25 Oct 90 02:42:34 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu>
Sender: news@milton.u.washington.edu
Distribution: na
Organization: Mendou Zaibatsu, Tomobiki-Cho, Butsumetsu-Shi
Lines: 30

In article <9868@milton.u.washington.edu> iho@akbar.UUCP (Il Oh) writes:
>Correction.  _Anything_ (not almost) that can be done recursively can be done
>iteratively.  At the machine level, there is no such thing as recursion, so
>when you write recursive code, the compiler produces code that can be executed
>by a non-recursing CPU.  I'm pretty sure I'm right about this.

Sorry, this is not at all correct!

Recursion is nothing more a reentrant subroutine call.  Most modern
CPU's have support for a hardware stack, which is the most common way
of implementing recursion.  That is, subroutine calls are done by a
"push current PC on stack and jump" instruction, subroutine returns by
a "pop PC from stack" instruction, and local variable creation by an
"allocate space on stack" instruction.  Many CPU's also have a "push
value on stack" and "pop value from stack" instruction, but these are
less commonly used today than the space-allocation instructions.

Machines without hardware stack instructions can emulate them.

What I think you are thinking of are compilers which are smart enough
to recognize tail-recursion and to generate iterative instead of
recursive code.

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ MRC@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.