Rekurzija

Naloga: štejemo liste

Dan je podatkovni tip dvojiški dreves:

type 'a tree = Leaf of a | Node of 'a tree * 'a tree

Sestavite funkcijo

count : ('a -> bool) -> 'a tree -> int

ki sprejme predikat p in dreveo t ter vrne število listov v drevesu t, ki ustrezajo predikatu p.

- count (fun x -> x > 2) (Node (Node (Leaf 2, Leaf 4), Node (Leaf 1, Node (Leaf 3, Leaf 0)))) ;;
- : int = 2

Naloga: Pascalov trikotnik

Sestavite funkcijo

pascal : int -> int list list

ki sprejme pozitivno celo število n in vrne prvih n vrstic Pascalovega trikotnika:

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
  ...........

Na primer, pascal 3 vrne

[[1], [1,1], [1,2,1]]