Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question

closed as unclear what you're asking by Peter Taylor, Clyde Lobo, Jan Dvorak, Geobits, Kyle Kanos Jun 16 at 14:35

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

    
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 Büttner Jun 16 at 11:25
1  
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 at 11:28
2  
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 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 at 12:03
3  
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 at 13:26

7 Answers 7

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

share|improve this answer
    
Can you explain a bit how this works? –  Alessandro Jun 16 at 11:41
3  
Upvoted for the sheer nerve to use this method in C, of all languages ;) –  Tal Jun 16 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.

share|improve this answer
1  
Short circuit evaluation looks suspiciously like control flow. –  James_pic Jun 16 at 11:33
1  
@James_pic True, but the question specifically mentions it as valid. –  Tal Jun 16 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 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 at 12:07
    
Technically, || can control flow (try 0 || alert("OH NOES") versus 1 || alert("OH NOES")) –  James_pic Jun 16 at 12:11

Haskell

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.

share|improve this answer
    
Since the OP specifically allowed poymorphism, and Haskell implements polymorphism via run-time pattern matching, this seems legit. –  James_pic Jun 16 at 11:59
1  
"Recursion without a base case" - isn't fib 0 = 0 base case? –  Davor Jun 16 at 12:13
    
@Davor: There is no control flow statement here, so I think this entry is valid. –  n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Jun 16 at 12:33
2  
Yes, but there is a base case. You need to obey all the rules, not just some. –  Davor Jun 16 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 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;
    }
share|improve this answer
    
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 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 at 14:15
    
You may be right - the question is not very clear. –  Paul R Jun 16 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.

share|improve this answer
    
Fun fact, True == 1 and False == 0 so the int is redundant. –  Sieg Jun 16 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 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.

share|improve this answer

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.
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.