CODEWITHSUNDEEP
recursionfunctional-programmingocaml
REALFREE
REALFREE

Reputation: 4396

tail recursion vs. forward recursion

Can someone give me the difference between these two kinds recursions and example (specifically in OCaml)?

Upvotes: 26

Views: 28067

Answers (3)

Pandemonium
Pandemonium

Reputation: 8390

For example, a recursive function build_word which takes a char list and combine them to a string i.e.['f'; 'o'; 'o'] to string "foo". The induction process can be visualized this way:

build_word ['f'; 'o'; 'o']
"f" ^ (build_word ['o'; 'o'])
"f" ^ ("o" ^ (build_word ['o'])    // base case! return "o" and fold back
"f" ^ ("o" ^ ("o"))
"f" ^ ("oo")
"foo"

That was a normal recursion. Note that each pair of parentheses stands for a new stack frame or recursive call. The solution to this problem (i.e. "f", "fo", or "foo") cannot be derived before the end of the recursion (where the base case is met). Only then does the last frame return the last result back to the previous one before "popping", and vice versa.

In theory, each call creates a new stack frame (or scope, if you will) to hold the "place" for the fragmented solution to be returned and collected toward the beginning. This can leads to stackoverflow (this link is a recursion btw).

A tail call version would look something like this:

build_word ['f'; 'o'; 'o'] ""
build_word ['o'; 'o'], "f"
build_word ['o'] ("f" ^ "o")
build_word [] ("f" ^ "o" ^ "o")
"foo"

Here, the accumulated result (often stored in a variable known as accumulator) is being passed forward. With optimization, tail call wouldn't have to create a new stack frame because it does not have to maintain the previous ones. The solution is being solved "forward" rather than "backward".

Here are the build_word functions in two versions:

non-tail

let build_word chars = 
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd :: tl -> build_word tl

tail

let build_word ?(acc = "") chars =
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd::tl -> build_word ~acc:(acc ^ Char.to_string hd) tl

The forward recursion is well-explained in the accepted answer by @sepp2k.

Upvotes: 0

sashang
sashang

Reputation: 12194

Here's an example of a tail recursive factorial function:

let fac n =
  let rec f n a =
    match n with
      0 -> a
    | _ -> f (n-1) (n*a)
  in
  f n 1

Here is it's non-tail recursive counterpart:

let rec non_tail_fac n =
  match n with
    0 -> 1
  | _ -> (non_tail_fac n-1) * n

The tail recursive function uses an accumulator, a, to store the value of the result of the previous call. This allows OCaml to perform tail call optimization which results in the the stack not overflowing. Typically a tail recursive function will make use of an accumulator value to allow tail call optimization to occur.

Upvotes: 11

sepp2k
sepp2k

Reputation: 370112

A tail recursive function is a function where the only recursive call is the last one in the function. A non-tail recursive function is a function where that is not the case.

A backward recursion is a recursion where in each recursive call the value of the parameter is less than in the previous step. A forward recursion is a recursion where it grows bigger with each step.

Those are two orthogonal concepts, i.e. a forward recursion may or may not be tail-recursive and the same applies to backward recursions.

For example the factorial function is often written like this in imperative languages:

fac = 1
for i from 1 to n:
    fac := fac * i

The common recursive version of factorial counts backwards (i.e. it calls itself with n-1 as the parameter), however if you'd directly translate the above imperative solution, you'd come up with a recursive version that counts upwards. It would look something like this:

let fac n =
  let rec loop i =
    if i >= n
    then i
    else i * loop (i+1)
  in
    loop 1

This is a forward recursion and as you can see it is slightly more cumbersome than the backward recursive variant as it requires a helper function. Now this is not tail recursive as the last call in loop is the multiplication, not the recursion. So to make it tail-recursive, you'd do something like this:

let fac n =
  let rec loop acc i =
    if i >= n
    then acc
    else loop (i*acc) (i+1)
  in
    loop 1 1

Now this is both a forward recursion and a tail recursion because the recursive call is a) a tail-call and b) calls itself with a greater value (i+1).

Upvotes: 36

Related Questions