3 ms·
I believe you can fairly easily spot recursive search tree implementations in the wild, in production code. Compilers and interpreters often use recursion, and
by kazinator 5y ago
I believe you can fairly easily spot recursive search tree implementations in the wild, in production code.
Compilers and interpreters often use recursion, and that goes to as many levels as the program requires.
Garbage collectors that use recursion to traverse the reachable objects are not unheard of.
Reference counting smart pointers are recursive. E.g. when we call object->dropReference(), and the refcount goes to zero, that may trigger otherObject->dropReference().
In C++, recursion is built into the language; e.g. destroying an object can trigger a cascade of recursive destructor calls. The object may have members which are smart pointers; those get destroyed, and may cause their referenced objects to get recursively destroyed.
Have you heard of a "recursive descent parser"? GNU C++ uses one (a huge source file written in C++, well over a megabyte long). This will recurse as deeply as the program's nesting goes; C++ programs often go to more than three levels of nesting. (There are some non-recursive hacks mixed in there, like some operator precedence parsing involving an explicit stack: Shunting-Yard or similar?)
https://github.com/gcc-mirror/gcc/blob/master/gcc/cp/parser.c https://github.com/gcc-mirror/gcc/blob/master/gcc/cp/parser....
Let's switch over to embedded. Have you heard of BusyBox? BusyBox provides scaled down system utilities for embedded systems. It is very widely used.
BusyBox's "libb" internal library contains a function called "recursive_action" for walking file system trees. This is actually recursive, and frequently goes more than three levels deep in actual use:
https://github.com/brgl/busybox/blob/master/libbb/recursive_action.c https://github.com/brgl/busybox/blob/master/libbb/recursive_...
This is used by BusyBox programs like mdev (udev replacement) lsusb, lspci, chmod, netstat, grep, tar, ...
Also, HN isn't a good place to exhibit Lisp condescension/ignorance.