[plt-scheme] Recursion to iteration

On Apr 3, 2010, at 11:50 PM, Andrei Estioco wrote:

> 've been told that syntactically recursive functions can be written as (while or for) loops. 


Whoever told you that was trying to confuse you. Here are two explanations of why it is plain wrong and plain true. 

1. Since _all_ recursive functions are rewritten as machine code, and since machine code doesn't include recursion, it is obviously true that all recursive functions can be written with some form of loop. Here is how you do it: 

-- cps 
-- convert closures to data structures 
-- convert function definitions to labels 
-- introduce global label variable 
-- convert function calls to label setting 
-- run in while loop until label setting is 'exit'

For details, see EOPL, PLAI, and other books like that. 

2. It's not true at all. To make this statement relevant, you need to restrict what counts as "written as". Depending on what restriction you choose it is possible to write some struct rec functions as loops and some gen rec functions, too, but not all of them. Indeed I conjecture that no matter which restriction you choose, this statement remains true, but I will admit that I am not interested in proving it. (The reason is that struct rec allows all kinds of 'clean' exits and while/for/do loops don't.)

-- Matthias