Just for completeness, ls is part of GNU coreutils: www.gnu.org/software/coreutils/.

There are, in effect, two closely coupled questions you may be asking.

• Why is the process of walking to each entry in a filesystem hierarchy an inherently recursive process? This is addressed by the other answers, such as Zanna's and Kaz Wolfe's.
• How is the technique of recursion used in the implementation of ls? From your phrasing ("How is recursion used in the process?"), I think this is part of what you want to know. This answer addresses that question.

Why it makes sense for ls to be implemented with a recursive technique:

FOLDOC defines recursion as:

When a function (or procedure) calls itself. Such a function is called "recursive". If the call is via one or more other functions then this group of functions are called "mutually recursive".

The natural way to implement ls is to write a function that constructs a list of filesystem entries to be displayed, and other code to process path and option arguments and to display the entries as desired. That function is highly likely to be implemented recursively.

During option processing, ls will determine if it has been asked to operate recursively (by being invoked with the -R flag). If so, the function that builds a list of entries to be displayed will call itself once for each directory it lists, except . and ... There may be separate recursive and nonrecursive versions of this function, or the function may check each time if it is supposed to be operating recursively.

Ubuntu's /bin/ls, the executable that runs when you run ls, is provided by GNU Coreutils, and it has many features. As a result, its code is somewhat longer and more complicated than you might expect. But Ubuntu also contains a simpler version of ls, provided by BusyBox. You can run this by typing busybox ls.

How busybox ls uses recursion:

ls in BusyBox is implemented in coreutils/ls.c. It contains a scan_and_display_dirs_recur() function that is invoked to print a directory tree recursively:

static void scan_and_display_dirs_recur(struct dnode **dn, int first)
{
    unsigned nfiles;
    struct dnode **subdnp;

    for (; *dn; dn++) {
        if (G.all_fmt & (DISP_DIRNAME | DISP_RECURSIVE)) {
            if (!first)
                bb_putchar('\n');
            first = 0;
            printf("%s:\n", (*dn)->fullname);
        }
        subdnp = scan_one_dir((*dn)->fullname, &nfiles);
#if ENABLE_DESKTOP
        if ((G.all_fmt & STYLE_MASK) == STYLE_LONG || (G.all_fmt & LIST_BLOCKS))
            printf("total %"OFF_FMT"u\n", calculate_blocks(subdnp));
#endif
        if (nfiles > 0) {
            /* list all files at this level */
            sort_and_display_files(subdnp, nfiles);

            if (ENABLE_FEATURE_LS_RECURSIVE
             && (G.all_fmt & DISP_RECURSIVE)
            ) {
                struct dnode **dnd;
                unsigned dndirs;
                /* recursive - list the sub-dirs */
                dnd = splitdnarray(subdnp, SPLIT_SUBDIR);
                dndirs = count_dirs(subdnp, SPLIT_SUBDIR);
                if (dndirs > 0) {
                    dnsort(dnd, dndirs);
                    scan_and_display_dirs_recur(dnd, 0);
                    /* free the array of dnode pointers to the dirs */
                    free(dnd);
                }
            }
            /* free the dnodes and the fullname mem */
            dfree(subdnp);
        }
    }
}

The line where the recursive function call takes place is:

                    scan_and_display_dirs_recur(dnd, 0);

Seeing the recursive function calls as they happen:

You can see this in operation if you run busybox ls in a debugger. First install the debug symbols by enabling -dbgsym.ddeb packages and then installing the busybox-static-dbgsym package. Install gdb as well (that's the debugger).

sudo apt-get update
sudo apt-get install gdb busybox-static-dbgsym

I suggest debugging coreutils ls on a simple directory tree.

If you don't have one handy, make one (this works the same way as the mkdir -p command in WinEunuuchs2Unix's answer):

mkdir -pv foo/{bar/foobar,baz/quux}

And populate it with some files:

(shopt -s globstar; for d in foo/**; do touch "$d/file$((i++))"; done)

You can verify busybox ls -R foo works as expected, producing this output:

foo:
bar    baz    file0

foo/bar:
file1   foobar

foo/bar/foobar:
file2

foo/baz:
file3  quux

foo/baz/quux:
file4

Open busybox in the debugger:

gdb busybox

GDB will print some information about itself. Then it should say something like:

Reading symbols from busybox...Reading symbols from /usr/lib/debug/.build-id/5c/e436575b628a8f54c2a346cc6e758d494c33fe.debug...done.
done.
(gdb)

(gdb) is your prompt in the debugger. The first thing you'll tell GDB to do on this prompt is to set a breakpoint at the start of the scan_and_display_dirs_recur() function:

b scan_and_display_dirs_recur

When you run that, GDB should tell you something like:

Breakpoint 1 at 0x5545b4: file coreutils/ls.c, line 1026.

Now tell GDB to run busybox with ls -R foo (or whatever directory name you want) as its arguments:

run ls -R foo

You may see something like this:

Starting program: /bin/busybox ls -R foo

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6c60, first=1) at coreutils/ls.c:1026
1026    coreutils/ls.c: No such file or directory.

If you do see No such file or directory, as above, that's okay. The purpose of this demonstration is just to see when the scan_and_display_dirs_recur() function has been called, so GDB doesn't need to examine the actual source code.

Notice that the debugger hit the breakpoint even before any directory entries were printed. It breaks on the entrace to that function, but the code in that function must run for any directories to be enumerated for printing.

To tell GDB to continue, run:

c

Each time scan_and_display_dirs_recur() is called, the breakpoint will be hit again, so you will get to see recursion in action. It looks like this (including the (gdb) prompt and your commands):

(gdb) c
Continuing.
foo:
bar    baz    file0

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cb0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/bar:
file1   foobar

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cf0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/bar/foobar:
file2

foo/baz:
file3  quux

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6cf0, first=first@entry=0) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.

foo/baz/quux:
file4
[Inferior 1 (process 2321) exited normally]

The function has recur in its name... does BusyBox only use it when the -R flag is given? In the debugger, this is easy to find out:

(gdb) run ls foo
Starting program: /bin/busybox ls foo

Breakpoint 1, scan_and_display_dirs_recur (dn=dn@entry=0x7e6c60, first=1) at coreutils/ls.c:1026
1026    in coreutils/ls.c
(gdb) c
Continuing.
bar    baz    file0
[Inferior 1 (process 2327) exited normally]

Even without -R, this particular implementation of ls uses the same function to find out what filesystem entries exist and show them.

When you want to quit the debugger, just tell it:

q

How scan_and_display_dirs_recur() knows if it should call itself:

Specifically how does it work differently when the -R flag is passed? Examining the source code (that may not be the exact version on your Ubuntu system) reveals that it checks its internal data structure G.all_fmt, where it stores what options it has been invoked with:

            if (ENABLE_FEATURE_LS_RECURSIVE
             && (G.all_fmt & DISP_RECURSIVE)

(If BusyBox has been compiled without support for -R, then it will also not attempt to display filesystem entries recursively; that's what the ENABLE_FEATURE_LS_RECURSIVE part is about.)

Only when G.all_fmt & DISP_RECURSIVE is true does the code that contains the recursive function call get run.

                struct dnode **dnd;
                unsigned dndirs;
                /* recursive - list the sub-dirs */
                dnd = splitdnarray(subdnp, SPLIT_SUBDIR);
                dndirs = count_dirs(subdnp, SPLIT_SUBDIR);
                if (dndirs > 0) {
                    dnsort(dnd, dndirs);
                    scan_and_display_dirs_recur(dnd, 0);
                    /* free the array of dnode pointers to the dirs */
                    free(dnd);
                }

Otherwise, the function just runs once (per directory specified on the command line).

ls -1 lists one file per line. By default, when it’s outputting to a terminal, ls lists files in columns, whose number varies depending on the length of the file names and the available space on screen.

To find this kind of information, man ls works better than ls --help. (This is true for most commands.)