Xref: utzoo comp.edu:3692 uw.general:1946
Path: utzoo!attcan!uunet!ogicse!milton!wiml
From: wiml@milton.u.washington.edu (William Lewis)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <9892@milton.u.washington.edu>
Date: 25 Oct 90 04:45:31 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu> <9882@milton.u.washington.edu>
Distribution: na
Organization: University of Washington, Seattle
Lines: 31

In article <9882@milton.u.washington.edu> mrc@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin) writes:
|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, ...

   But the CPU itself is iterative, not recursive. The CALL instruction
finishes when the subroutine begins, not when it ends.

|Machines without hardware stack instructions can emulate them.

   Precisely. Or the compiler could generate the emulating instructions
itself. As you said, the call is just a "push PC and jump" shorthand.
In either case, the recursive algorithm is being rewritten
non-recursively.


-- 
 wiml@milton.acs.washington.edu       Seattle, Washington   
     (William Lewis)   |  47 41' 15" N   122 42' 58" W  
"These 2 cents will cost the net thousands upon thousands of 
dollars to send everywhere. Are you sure you want to do this?"