recursive

Linux: Recursive file searching with grep -r (like grep + find)

Linux grep FAQ: How can I perform a recursive search with the grep command in Linux?

Solution: find + grep

For years I always used variations of the following Linux find and grep commands to recursively search subdirectories for files that match a grep pattern:

find . -type f -exec grep -l 'alvin' {} \;

This command can be read as, “Search all files in all subdirectories of the current directory for the string ‘alvin’, and print the filenames that contain this pattern.” It’s an extremely powerful approach for recursively searching files in all subdirectories that match the pattern I specify.

This is a page from my book, Functional Programming, Simplified

Tail-Recursive Algorithms in Scala

“Tail recursion is its own reward.”

From the “Functional” cartoon on xkcd.com.

Goals

The main goal of this lesson is to solve the problem shown in the previous lessons: Simple recursion creates a series of stack frames, and for algorithms that require deep levels of recursion, this creates a StackOverflowError (and crashes your program).

This is a page from my book, Functional Programming, Simplified

A Visual Look at JVM Stacks and Frames

Given the background information of the previous lesson, let’s take a visual look at how the JVM stack and stack frames work by going back to our recursive sum function from the previous lesson.

Before the sum function is initially called, the only thing on the call stack is the application’s main method:

Then main calls sum with List(1,2,3), which I show here without the “List” to keep things simple:

This is a page from my book, Functional Programming, Simplified

JVM Stacks and Stack Frames

For functions without deep levels of recursion, there’s nothing wrong with the algorithms shown in the previous lessons. I use this simple, basic form of recursion when I know that I’m working with limited data sets. But in applications where you don’t know how much data you might be processing, it’s important that your recursive algorithms are tail-recursive, otherwise you’ll get a nasty StackOverflowError.

For instance, if you run the sum function from the previous lessons with a larger list, like this:

This is a page from my book, Functional Programming, Simplified

Recursion: Thinking Recursively

“To understand recursion,
one must first understand recursion.”

Stephen Hawking

Goal

This lesson has one primary goal: to show that the thought process followed in writing the sum function follows a common recursive programming “pattern.” Indeed, when you write recursive functions you’ll generally follow the three-step process shown in this lesson.

Recursion: A Conversation Between Two Developers alvin May 29, 2017 - 11:07am

As an homage to one of my favorite Lisp books — an early version of what is now The Little Schemer — this lesson shows a little question and answer interaction that you can imagine happening between two Scala programmers.

Given this sum function:

def sum(list: List[Int]): Int = list match {
    case Nil => 0
    case x :: xs => x + sum(xs)
}

I hope this “conversation” will help drive home some of the points about how recursion works:

This is a page from my book, Functional Programming, Simplified

Recursion: Visualizing the recursive `sum` Function

Another way to view recursion is with visual diagrams. To demonstrate this, I’ll use this rectangular symbol in this lesson to represent a function:

The first step

Using that symbol and a list with only three elements, the first sum function call looks like this:

This is a page from my book, Functional Programming, Simplified

Recursion: How Recursive Scala Function Calls Work

An important point to understand about recursive function calls is that just as they “wind up” as they are called repeatedly, they “unwind” rapidly when the function’s end condition is reached.

In the case of the sum function, the end condition is reached when the Nil element in a List is reached. When sum gets to the Nil element, this pattern of the match expression is matched:

This is a page from my book, Functional Programming, Simplified

Recursion: How to Write a ‘sum’ Function in Scala

With all of the images of the previous lesson firmly ingrained in your brain, let’s write a sum function using recursion!

Sketching the sum function signature

Given a List of integers, such as this one:

val list = List(1, 2, 3, 4)

let’s start tackling the problem in the usual way, by thinking, “Write the function signature first.”