Ask HN: Can recursion be more useful than regular loops?

https://news.ycombinator.com/item?id=46016892

by DenisDolya • 8 months ago

5 5 8 months ago

news.ycombinator.com

rossdavidh• 8 months ago

The times I've found it useful are for walking org charts or file folders, which are of unknown depth and match neatly into a recursive approach.

ArtRasel3• 8 months ago

Main Folder/ ├── Subfolder 1/ │ ├── File A │ └── Subfolder 1.1/ │ └── File B └── Subfolder 2/ └── File C

ArtRasel3• 8 months ago

Recursion vs Loops - Android Development Perspective

In Android development, both have their places, but recursion shines in specific scenarios:

Where recursion works better: • File System Traversal - Scanning nested app directories and external storage • View Hierarchy Processing - Traversing through complex ViewGroup structures • JSON/XML Parsing - Handling nested data structures from API responses

Practical Android Example: fun findAllImageFiles(dir: File): List<File> { val imageFiles = mutableListOf<File>() dir.listFiles()?.forEach { file -> if (file.isDirectory) { imageFiles.addAll(findAllImageFiles(file)) // Recursion } else if (file.isImageFile()) { imageFiles.add(file) } } return imageFiles }

When to prefer loops: • Performance-critical tasks (avoid StackOverflowError) • Simple iterations with known depth • Memory-constrained environments

Key Insight: Recursion provides cleaner code for tree-like structures, while loops are better for linear tasks. Choose based on data structure complexity rather than personal preference.

ArtRasel3• 8 months ago

fun findAllImageFiles(dir: File): List<File> { val imageFiles = mutableListOf<File>() dir.listFiles()?.forEach { file -> if (file.isDirectory) { imageFiles.addAll(findAllImageFiles(file)) // } else if (file.isImageFile()) { imageFiles.add(file) } } return imageFiles }

btilly• 8 months ago

It depends on what you consider "more useful".

First, anything that you can do with recursion, you can do without. This is trivially obvious to anyone who knows that any Turing complete language can simulate any other, and therefore there is an equivalence of what they can do. And this is demonstrated in practice when you consider that every language with recursion, is ultimately implemented in machine language. Which doesn't have recursion.

That said, the concept of recursion can allow us to think about and solve problems that we would otherwise find challenging to think about. This is fundamental to how programming works. We build abstractions on top of lower primitives. These abstractions then make it easier to think about and solve our problems. We could have done the same thing without the abstraction. But it would have taken more work, and it would be harder for us to keep that well-organized.

The widespread popularity of languages with recursion demonstrates that it is a useful abstraction.

But let's pull back the curtain. What recursion does for us is allow us to organize our computation using the call stack. What we do implicitly using the call stack, can always be done instead using an explicit stack. The code looks different, but is actually equivalent.

The value of knowing how to do that is that we then can ask what happens if we choose to replace the stack with something else. For this example, let's add a caching layer on top of the recursion. This gives us a top-down dynamic programming algorithm. It is doing a depth-first search. If we replace the stack with a queue, we get a breadth-first search. If we replace it with the right priority queue instead, we get an A*-search. If we go back to the breadth-first search and optimize to throw away data as soon as we are done with it, we can get a bottom-up dynamic programming algorithm.

Therefore recursion is absolutely a valuable tool in your mental toolbox. But it becomes even more powerful if you know how to implement it with loops, and then know how to manipulate that, we can get a whole set of powerful tools that recursion alone does not give you.

Ask HN: Can recursion be more useful than regular loops?

Related Stories