Publisher's Synopsis
Excerpt from A Linear-Time Algorithm for the Weighted Median Problem
In order to improve the running time of these procedures, we eliminated the recursion by explicitly using a stack. Procedure wtselect is only tail-recursive, i.e., the recursive call to wtselect is the last instruction in the body of the procedure; select, the regular median routine, has, however, both tail recursion and a recursive call to find the median of the median strip. Eliminating tail recursion is trivial. All that needs to be done is to reinitialize the parame ters to the values of the new call and transfer control to the start of the procedure. Eliminating a recursive call from the middle of a procedure is more complicated since upon return from the recursive call the procedure must resume computation with the 0' iginal parameters and local vari ables. In general, the recursive call will change the values of the variables it accesses. Therefore, the current values of the parameters and a l local variables must be saved on a stack. Then the recursive call can be initiated by reii -aliz; rg parameters and transferring control to the start of the procedure. In this way, upon return from a recursive call the values of the parameters and local variables at a previous level of recursion can be retrieved by popping the stack and the cal ling environment can be restored.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.