# Is it correct to say that fold_left corresponds to tail recursion and fold_right to forward recursion?

I am curious. Is there a correspondence between `fold_left` and `fold_right` with tail and forward recursion?

I was reading some code for manual implementations of them and it seems fold_right implements forward recursion and fold_left implements forward. Is that right?

`````` let rec fold_left f a list =
match list
with
| [] -> a
| (x :: xs) -> fold_left f (f a x) xs;;
``````
`````` let rec fold_right f list b =
match list
with [] -> b
| (x :: xs) -> f x (fold_right f xs b);;
``````

since it seems that fold right starts executing only until it reaches the end of the list (the right end, which I am assuming this is why its called fold right). But starts collecting a compound collection computations of `f x (recurse)` that don’t get executed until the end. i.e. the recursion is done first.

With fold left it seems the computation is done FIRST then the recursion. I say that cuz we have

`````` fold_left f (f a x) xs
``````

so we have to compute `(f a x)` first for the whole fold_left thing to even begin executing. Which reminds me of tail recursion. Since we are pass the value to compute first.

`fold_left` starts from the left (beginning of the list) and is tail-recursive. `fold_right` starts from the right (end of the list) and is not tail-recursive. See the manual of the List module.

1 Like