<- People Behind Informatics


All 0-9 A B C D E F G H I J K L M N O P Q R S T U V W XY Z




 
Recursive Procedure Call
Recursive functions played an important role in mathematics even before the age of digital computers. Digital computers made it possible not only to formulate, but also to execute recursive functions. From the execution point of view we speak of recursion when the procedure-call chain contains a circle. If the “length” of the circle is 1 (a procedure directly calls itself) then we speak about direct recursion, otherwise about indirect recursion (if e.g. P1 calls P2, P2 calls P3 and P3 calls again P1, we have a circle of length 3). For a while it was not obvioushow recursion could be implemented efficiently, which was the primary reason why early programming languages avoided recursion. At each call, a new instance of a so-called activation record (containing the parameters, the local variables and some state information) must be created. Thus, if the recursive call is repeated N-times (has the depth N) N activation records must be alive, whereby only the very last one can be accessed. Dijsktra recognized that this kind of behavior is exactly that which is characteristic of a first-in, last-out queue (later dubbed stack by him). On a call, the corresponding activation record can be simply pushed on a stack. On return, it is popped and the storage is regained. N consecutive calls produce a stack of the depth N. The activation record of the currently running procedure is always on the top of the stack. This is an extremely efficient storage management (sometimes also called semi-dynamic storage). [Source: Laszlo Böszörmenyi: Notes to the Virtual Exhibition "People behind Informatics"]
 

 

<- People Behind Informatics


Home  |  Top  |  Search  |  Gallery  | Glossary  | Sitemap  |  Making Of  |  Help