𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of recursion in problem-solving

✍ Scribed by M.C. Er

Publisher
Elsevier Science
Year
1984
Weight
426 KB
Volume
20
Category
Article
ISSN
0020-7373

No coin nor oath required. For personal study only.

✦ Synopsis

The importance of paying attention to the complexity of recursion in problem solving is stressed. Many ill-founded beliefs and doctrines on constructing recursive algorithms are challenged. The Tower of Hanoi problem and its variant are used as concrete examples for illustrating that many seemingly correct recursive algorithms are, indeed, invalid or non-optimal. A simple context-free grammar for generating strings of balanced parentheses is then used to show the difficulty of programming recursive algorithms in block-structured languages. Other factors contributing to the difficulty in understanding recursive algorithms implemented in block-structured languages are also identified. It is suggested that more research needs to be done to foster the science of recursive programming.

πŸ“œ SIMILAR VOLUMES

On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

On the complexity of the car sequencing
On the complexity of the car sequencing problem
✍ TamΓ‘s Kis πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 190 KB

In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a su cient condition of membership of NP. We also provide a ps