Problem with recursion? (was [plt-scheme] Re: Novice needs help writing function )

From: Matthias Felleisen (matthias at
Date: Fri Jan 4 15:28:28 EST 2008

On Jan 4, 2008, at 1:41 PM, Yavuz Arkun wrote:

> The number of explicit variables in the recursive version is  
> deceptive. When I am trying to understand a program, I put myself  
> in the place of the computer and work through the program in my  
> mind. For the iterative version, everything I need to remember are  
> explicitly named. For recursive algorithms, I need to keep track of  
> the implicit variables as well, such as how deep I am into the  
> recursion, and what the intermediate values are, because I will  
> need them on my way back.
> Personally, I can manage 1 or 2 levels mentally, and if I use pen  
> and paper maybe a few more. After that, I need to take a leap of  
> faith, and inductively conclude that if it works for the simplest  
> case, and for the one after that, it should work for all cases.
> In other words, neither the conciseness of the program text, nor  
> the elegance of the expressed ideas necessarily means "easy to  
> understand", unless you are prepared to take the leap.
> I can do that, because I know recursion works as a general concept.  
> It may be more difficult if you are new to the idea. Even more so,  
> when you realize that the 'elegant' method can have rather  
> inelegant space and/or time characteristics. Then you start to feel  
> like you must be missing something and become frustrated.
> Therefore, recursion (like any other method) should be illustrated  
> using examples that can be best solved with recursion.

Please do take a look at HtDP. Your message suggests that you were  
trained by or as an EE :-)

-- Matthias

Posted on the users mailing list.