Tail recursion
Now that we've covered recursion, we can dive into tail recursion. Tail recursion is when a subroutine call is performed as the final action of a procedure:
Let's take a look at the following implementations of factorial. The first is recursive, but not tail recursive. The second is implemented using tail recursion.
Let's take a look at the following implementations of factorial. The first is recursive, but not tail recursive. The second is implemented using tail recursion.
let rec factorial : int -> int = fun num ->
if num > 1
then num * factorial (num - 1)
else 1
;;
let factorial : int -> int = fun num ->
let rec helper : int -> int -> int = fun n acc ->
if n > 0
then helper (n-1) (acc * n)
else acc
in
helper num 1
;;
The bolded section are the tail calls. They are recursive calls; thus, tail recursion!
Also of note, we've defined a helper function called helper inside the declaration of factorial that does all of the work of the function. The outer "shell" function simply calls the helper function with the appropriate arguments. We've implemented factorial this way because we don't need to access the helper function outside of the function and because we want factorial to have the same type signature--you'll notice that our helper function requires 2 arguments to work, one being the accumulator.
Also of note, we've defined a helper function called helper inside the declaration of factorial that does all of the work of the function. The outer "shell" function simply calls the helper function with the appropriate arguments. We've implemented factorial this way because we don't need to access the helper function outside of the function and because we want factorial to have the same type signature--you'll notice that our helper function requires 2 arguments to work, one being the accumulator.
So What?
Functional Languages are built to take advantage of tail recursion. The nice property of calling another function as its last step is that the call can be done without adding a stack frame to the stack! As a result we can make do with (near) constant stack space!
Let's take a look at how the stack works without tail recursion: Image taken from here.
Functional Languages are built to take advantage of tail recursion. The nice property of calling another function as its last step is that the call can be done without adding a stack frame to the stack! As a result we can make do with (near) constant stack space!
Let's take a look at how the stack works without tail recursion: Image taken from here.
As we can see, each time we recursively call factorial, we build up a stack frame. Each factorial call needs to wait for the next one to return and then does something with the return value. (We cover the stack/heap/memory more in depth here). By doing so, we are consuming more and more memory. In fact, the amount of memory we consume grows linearly with how large the input is, in our case, 4. However, in the case of tail recursion, each factorial call does not need to wait for the return value of the next call in order to do something with it. Instead, we can simply return that final value. As a result, we can simply replace the stack frame of each call.
Here, despite calling factorial multiple times, each time we call factorial, we do not need to build up a stack frame. By replacing the current stack frame, we can use less memory to do the same thing!
Some languages (like Python) do not replace the stack frame when doing tail calls but some optimizations of C do. However, making recursive functions tail recursive is a good programming practice in any programming language. Because OCaml has a good tail implementation, recursive functions should take advantage of this to be more efficient and so we don’t kill the stack. Let's take a look at the following function that makes lists of increasing integers.
let rec make_list : int -> int list = fun n -> - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12] |
Interesting notes about this make_list function. We have called List.append, a function in the List module in the standard library. We will be covering how to open Libraries (open) and calling functions from these libraries (Module.function) and some common functions a little later on.
Additionally, we have immediately put the value of n into an array by doing the following: [n]. |
This function functions perfectly well when we are making lists of 12 or so, but if we want to make a 10,000,000 element long list using this function, what happens?
make_list 10000000;;
Stack overflow during evaluation (looping recursion?).
We blow the stack (Stack Overflow). So, we've just seen how to use less stack space. So let’s make this implementation of make_list tail recursive:
let make_list : int -> int list = fun num ->
let rec helper = fun n acc ->
if n < 1
then acc
else helper (n - 1) (n :: acc)
in
helper num []
;;
make_list 10000000;;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59;
60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78;
79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97;
98; 99; 100; 101; 102; 103; 104; 105; 106; 107; 108; 109; 110; 111; 112;
113; 114; 115; 116; 117; 118; 119; 120; 121; 122; 123; 124; 125; 126; 127;
128; 129; 130; 131; 132; 133; 134; 135; 136; 137; 138; 139; 140; 141; 142;
143; 144; 145; 146; 147; 148; 149; 150; 151; 152; 153; 154; 155; 156; 157;
158; 159; 160; 161; 162; 163; 164; 165; 166; 167; 168; 169; 170; 171; 172;
173; 174; 175; 176; 177; 178; 179; 180; 181; 182; 183; 184; 185; 186; 187;
188; 189; 190; 191; 192; 193; 194; 195; 196; 197; 198; 199; 200; 201; 202;
203; 204; 205; 206; 207; 208; 209; 210; 211; 212; 213; 214; 215; 216; 217;
218; 219; 220; 221; 222; 223; 224; 225; 226; 227; 228; 229; 230; 231; 232;
233; 234; 235; 236; 237; 238; 239; 240; 241; 242; 243; 244; 245; 246; 247;
248; 249; 250; 251; 252; 253; 254; 255; 256; 257; 258; 259; 260; 261; 262;
263; 264; 265; 266; 267; 268; 269; 270; 271; 272; 273; 274; 275; 276; 277;
278; 279; 280; 281; 282; 283; 284; 285; 286; 287; 288; 289; 290; 291; 292;
293; 294; 295; 296; 297; 298; 299; ...]
Now make_list 10000000 will return with the proper value since we don’t consume that additional stack frame for each recursive call. Victory!
As seen with both factorial and make_list, to turn the initial function from recursive to tail recursive, we added a helper function and an accumulator. This is common practice to make functions tail recursive (List.fold_left vs. List.fold_right). We should be using the tail recursive fold_left.
Tail recursion is an important programming concept because it allows us to program recursively, but also because xkcd says it is. |