Ew statics ;) Tail recursion is of course only really useful if the host language supports tail recursion optimizations. I used a helper function:
```cpp
int findmin(int a[], int n)
{
if (n <= 0)
return -1; // arbitrary “no minimum” value, not really a good idea
else
findmin(a[0], a[1..n - 1], n - 1);
}
int findmin(int lastmin, int a[], int n)
{
if (n <= 0)
return lastmin;
else {
int currentmin = lastmin;
if (a[0] < currentmin)
currentmin = a[0];
findmin(currentmin, a[1..n - 1], n - 1);
}
}
```
You actually did a clever trick I'd forgotten about by using n as an index, avoiding copying the array. Solid goodness there, and here's an update of mine to do that:
```cpp
int findmin(int a[], int n)
{
if (n <= 0)
return -1; // arbitrary “no minimum” value, not really a good idea
else
return findmin(a[n - 1], a, n - 1);
}
int findmin(int lastmin, int a[], int n)
{
if (n <= 0)
return lastmin;
else {
int currentmin = lastmin;
if (a[n - 1] < currentmin)
currentmin = a[n - 1];
return findmin(currentmin, a, n - 1);
}
}
```
Implemented in Scala:
```scala
def findmin(a: List[Int]): Option[Int] = {
a match {
case first :: rest => findmin(first, rest)
case _ => None // otherwise
}
}
@scala.annotation.tailrec
def findmin(currentMin: Int, a: List[Int]): Option[Int] = {
a match {
case first :: Nil if currentMin < first => Some(currentMin)
case first :: Nil => Some(first)
case first :: rest if currentMin < first => findmin(currentMin, rest)
case first :: rest => findmin(first, rest)
case _ => None
}
}
```
The upside of the above is that the `@scala.annotation.tailrec` asks the compiler to double-check that we're tail recursive (we are :p). The Scala compiler will automatically optimize tail recursion regardless of whether the annotation is present. I also think it reads better ;)