# Not-endless Recursion without a base case [closed]

Write a recursive function/program, to calculate either the Factorial or the Fibonacci number of a given non-negative integer, without explicitly implementing the base case(s).

Your program/function must return/output the correct value in a reasonable time.

You cannot

1. Use if statement anywhere in your program/function, nor switch nor short-if-syntax (?:). Not even loops. Basically all control-flow statements are forbidden.

2. Use try, catch or exceptions of any kind.

3. Terminate the program (anything like exit(1)).

4. Use external sources (file, web, etc.)

5. Avoid recursion and return the proper value otherwise. (Your function must be recursive).

6. Use any of the standard loopholes.

You can

• Use polymorphism, create threads, wrap the Integer type with your own class, or use any other mechanism your language or runtime has. (I can think of a solution that uses the lazy-evaluation, for instance). The function/program can be written as more than one function, using Mutual Recursion, if it helps you.

Please provide a short explanation of what you did.

Be creative! The winning answer is the one with the most upvotes by 2014-06-23 (a week from today).

EDIT:

Some clarifications:

Using Pattern Matching in Functional Programming Languages is OK since it's considered as Polymorphism. The solution should be trivial though, so I guess it won't have the chance to win, since it is a . It is still a legitimate answer.

Although some may say it's flow control in disguise, using lazy evaluation, (or short circuit evaluation) is allowed as well.

• Possibly a remote duplicate of this post on StackOverflow. I think a lot of answers there could be easily adapted to be valid submissions for this challenge. – Martin Ender Jun 16 '14 at 11:25
• The linked definition of control flow is such that any program with no control flow statements and with a recursive call must recurse infinitely. To avoid arguments, this needs a more precise definition of exactly what is permitted and what is forbidden, and it needs to cover all the language paradigms which people might want to use. – Peter Taylor Jun 16 '14 at 11:28
• The question should clarify whether or not it's legit to use functional languages' pattern matching, since factorial functions without apparent flow control are a textbook example for those. – Tal Jun 16 '14 at 11:30
• Thanks for the reference. If needed, this question can be protected or closed, as you see fit. I removed the link. I added a restriction for Functional languages. – Jacob Jun 16 '14 at 12:03
• This seems very language specific and it seems to be about how to write if any other than the standard way. E.g. is the Condition function of Mathematica permissible? What about short circuiting &&? What's not clear to me here is the principle behind accepting or rejecting a solution. You only have a list of acceptable solution, most of which apply only to certain languages. Less usual constructs that might be specific to a language are not mentioned. – Szabolcs Jun 16 '14 at 13:26

# C - factorial

simple as that

int not_factorial(int n){return 1;}
int factorial(int n)
{
int (*maybe_factorial[])(int) = {factorial, not_factorial};
return n*maybe_factorial[!(n-1)](n-1);
}


the function factorial is almost like a basic recursive approach but not_factorial only returns 1.
If I create an array of function pointers (0: fac, 1: not_fac), then I can control which one should be executed at the next call:
maybe_factorial[0](n-1) calls factorial
maybe_factorial[1](n-1) calls not_factorial.
!(n-1) means if n > 1 return 0 else return 1

• Can you explain a bit how this works? – user25169 Jun 16 '14 at 11:41
• Upvoted for the sheer nerve to use this method in C, of all languages ;) – Tal Jun 16 '14 at 11:59

# Javascript

Just a quick idea to get things going, nothing too fancy:

var t = [1];

function factorial (n) {
var h = arguments[1] ||  1;
t.push (t[t.length-1] * h);
return t[n] || factorial (n,h+1);
}


This should be considered a program rather than a function, because it depends on a variable that is outside the function's scope (and it only works once), but I'll try to edit it later as a proper closure.

The trick here relies on the combination of JS's lazy evaluation and the fact that undefined object properties are merely an undefined value rather than a reason to throw an error. Rather than doing a boring recursion down from n to 0, I've decided to add a "secret" second parameter (arguments[1]) as a counter from 1 to n. Each iteration multiplies the last element of the t array by the counter, to fill the array with all the factorial values, and once the array has an nth element I stop the recursion and return it.

• Short circuit evaluation looks suspiciously like control flow. – James_pic Jun 16 '14 at 11:33
• @James_pic True, but the question specifically mentions it as valid. – Tal Jun 16 '14 at 11:34
• excuse me but h = arguments[1] || 1 means h = arguments[1] ? arguments[1] : 1 and this applies to the second occurrence also. (i may be wrong but i always used it this way) – bebe Jun 16 '14 at 11:58
• @bebe h = arguments[1] || 1 does not control the flow. It's just an operator, with two pretty simple operands. By this logic, I shouldn't be able to use any operators at all, because their result depends on the operands' values, e.g. 1+1 does not give the same result as 2+2. As for the second occurrence, as I said, the question specifically mentioned it as valid. – Tal Jun 16 '14 at 12:07
• Technically, || can control flow (try 0 || alert("OH NOES") versus 1 || alert("OH NOES")) – James_pic Jun 16 '14 at 12:11

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)


Thanks to pattern matching, there is no need for control structures in this function.

As Tal mentionned, this is a textbook example for functional languages, one of the first shown when learning them.

• Since the OP specifically allowed poymorphism, and Haskell implements polymorphism via run-time pattern matching, this seems legit. – James_pic Jun 16 '14 at 11:59
• "Recursion without a base case" - isn't fib 0 = 0 base case? – Davor Jun 16 '14 at 12:13
• @Davor: There is no control flow statement here, so I think this entry is valid. – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 16 '14 at 12:33
• Yes, but there is a base case. You need to obey all the rules, not just some. – Davor Jun 16 '14 at 13:07
• @Davor : None of the 6 "You cannot"-rules are broken here. This entry is as valid as the other ones, and all of them define a base case. – cpri Jun 16 '14 at 14:49

# C++

#include <iostream>
using namespace std;

template <int K>
class Int
{
public :
int Fact(void);
};

template<>
int Int<0>::Fact()
{
return 1;
}

template<int K>
int Int<K>::Fact()
{
Int <K-1> x;
return K*x.Fact();
}

int main(void)
{
Int<5> A;

cout << A.Fact() << endl;
}

• It looks like you are explicitly implementing the base case though, which is proscribed in the first paragraph of the question ? – Paul R Jun 16 '14 at 13:58
• As I understand the question, explicitly implementing the base case means writing something like if (K==0) return 1;. All answers define 0! or 1! in a way. Mine could be more obfuscated, though. – cpri Jun 16 '14 at 14:15
• You may be right - the question is not very clear. – Paul R Jun 16 '14 at 14:16

# Python

f = lambda n: int(n==0) or n*f(n-1)


We exploit the short-circuiting behavior of or. For n=0, the base-case check returns true, which is converted to the int 1, and otherwise, the or expression evaluates to the recursive expression.

• Fun fact, True == 1 and False == 0 so the int is redundant. – seequ Jun 16 '14 at 15:47
• @TheRare I know, but someone might say that True is the wrong value for the factorial of 0 even though it converts to 1 in any arithmetic expression. – xnor Jun 16 '14 at 18:32

# Scala

Would this be the lazy solution the OP alluded to?

// Factorial
lazy val fac: Stream[Int] = 1 #:: Stream.from(1).map{i => i * fac(i - 1)}
// Fibonacci
lazy val fib: Stream[Int] = 0 #:: 1 #:: Stream.from(2).map{i => fib(i - 1) + fib(i - 2)}


Creates a lazily evaluated stream. The first elements are hard-coded, but subsequent elements are defined recursively, with no control flow. As a side effect, values are memo-ised.

## Tcl

Well, if we can't use if or switch or for or while to test then it looks like we'll have to implement our own if.

I personally feel re-implementing if is a bit more impressive than polymorphism because polymorphism (or function overloading) is still using built in language feature. What I'm doing is implementing a feature from scratch!

# First we write functions called 0 and 1
proc 0 {a b} {uplevel 1 $b} proc 1 {a b} {uplevel 1$a}

# Now we try to implement IF, we'll call it _I_F_
proc _I_F_ {statement a b} {
uplevel 1 [list [expr $statement]$a $b] } # Now lets write a recursive countdown function # using our scratchbuilt if: proc countdown {number} { puts$number
_I_F_ "$number>0" "count [expr$number-1]" "puts done"
}

# Lets see if it works:
countdown 10 ;# should count down to 0


Notes:

• uplevel is like evel only it allows you to execute the code in any stack level you chose.
• Tcl always expects a function name to be the first word of a statement. Therefore if you want to evaluate something like $a>$b or $a==$b you can't because you can't start a statement with a variable. That's what expr is for - it's a function that evaluates expressions.
• Comparison expressions such as $a<$b, like in other languages, return true or false. In tcl true is canonically 1 and false is canonically 0. So the expr \$statement returns 0 or 1.
• We then construct a statement using list which, depending on the expr will start with 0 or 1 and uplevel it. This in turn executes either the function 0 or the function 1.