Tail Recursion Error: Expression has type int but an expression was expected of type unit

Question

I just started programming with the OCaml functional programming language for one of my classes at school. One of our problems was to write whats known as a "Russian Peasant Algorithm" but using tail recursion instead of normal recursion. I think I've almost got it, but I keep running into a silly error that I can't seem to pinpoint stating; "This expression has type int but an expression was expected of type unit" over the line "aux x (base*base) (power/2)". I'm really not sure how to go about fixing this as I'm new to the syntax of the language. Any ideas?

I believe this to be caused by a conditional with no branch; however I have this implemented so I'm quite confused as to why its not working.

let even n = (n mod 2) = 0 ;;
let odd n = (n mod 2) = 1;; 

let exp_program (base, power) = 
  let rec func x base power =
    if base = 0 then 0
    else if power = 0 then x
    else if power = 1 then x*base
    else if (odd power) then
      func (x*base) (base*base) ((power-1)/2)
    else if (even power) then 
      func x (base*base) (power/2)
in  
func 1 base power ;;

The goal of this function is to call exp_program (2, 3) for example and have it produce the base^power. In this case it would result in 8

smac89 smac89 · Accepted Answer · 2019-01-17T22:53:52

You are missing the else clause.

Solution: Remove the last else if and replace with else.

let exp_program (base, power) = 
  let rec func x base power =
    if base = 0 then 0
    else if power = 0 then x
    else if power = 1 then x*base
    else if (odd power) then
      func (x*base) (base*base) ((power-1)/2)
    else 
      func x (base*base) (power/2)
in  
func 1 base power ;;

Tail Recursion Error: Expression has type int but an expression was expected of type unit

2 Answers