diff --git a/src/protocol/tests/eval_calls.rs b/src/protocol/tests/eval_calls.rs
index f9a1e3c7ff545504193df16b75442b85270fcb6e..9ed4d853b644228943a8fbf8ea4ba3c7eb4dd136 100644
--- a/src/protocol/tests/eval_calls.rs
+++ b/src/protocol/tests/eval_calls.rs
@@ -27,6 +27,58 @@ fn test_function_call() {
     });
 }
 
+#[test]
+fn test_recursion() {
+    // Single-chain
+    Tester::new_single_source_expect_ok("factorial", "
+    func horribly_slow_factorial(u32 term) -> u32 {
+        if (term <= 0) { return 1; }
+
+        return term * horribly_slow_factorial(term - 1);
+    }
+    func foo() -> u32 {
+        return horribly_slow_factorial(10);
+    }
+    ").for_function("foo", |f| {
+        f.call_ok(Some(Value::UInt32(3628800)));
+    });
+
+    // Multi-chain horribleness
+    Tester::new_single_source_expect_ok("fibonacci", "
+    func horribly_slow_fibo(u32 term) -> u32 {
+        if (term <= 1) {
+            return 1;
+        }
+        return horribly_slow_fibo(term - 2) + horribly_slow_fibo(term - 1);
+    }
+    func foo() -> u32 {
+        return horribly_slow_fibo(10);
+    }").for_function("foo", |f| {
+        f.call_ok(Some(Value::UInt32(89)));
+    });
+
+    // Mutual recursion (in a contrived fashion, ofcourse)
+    Tester::new_single_source_expect_ok("mutual recursion", "
+    func collatz_even(u32 iter, u32 value) -> u32 {
+        value = value / 2;
+        if (value % 2 == 0) return collatz_even(iter + 1, value);
+        else                return collatz_odd(iter + 1, value);
+    }
+    func collatz_odd(u32 iter, u32 value) -> u32 {
+        if (value <= 1) return iter;
+
+        value = 3 * value + 1;
+        if (value % 2 == 0) return collatz_even(iter + 1, value);
+        else                return collatz_odd(iter + 1, value);
+    }
+    func foo() -> u32 {
+        return collatz_odd(1, 19);
+    }
+    ").for_function("foo", |f| {
+        f.call_ok(Some(Value::UInt32(21)));
+    });
+}
+
 #[test]
 fn test_empty_blocks() {
     // Yes this is silly, but I managed to make this a bug before