Open AccessLook Ma, Backtracking without Recursion
Author(s) -
T Tom Verhoeff
Publication year - 2021
Publication title -
olympiads in informatics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.13
H-Index - 12
eISSN - 2335-8955
pISSN - 1822-7732
DOI - 10.15388/ioi.2021.10
Subject(s) - backtracking , recursion (computer science) , object (grammar) , computer science , stack (abstract data type) , function (biology) , loop (graph theory) , programming language , mathematics , theoretical computer science , calculus (dental) , algorithm , discrete mathematics , algebra over a field , combinatorics , pure mathematics , artificial intelligence , evolutionary biology , biology , medicine , dentistry
I show how backtracking can be discovered naturally without using a recursive function(nor using a loop with an explicit stack). Rather, my approach involves a form of self application that can be elegantly expressed in an object-oriented program, and that is reminiscent of how recursion is done in lambda calculus. It also illustrates why reasoning about object-oriented programs can be hard.