• Create Account

### #Actualalvaro

Posted 03 July 2012 - 11:21 AM

I think it is unfortunate that the example of Fibonacci is what most people remember when thinking of recursive functions, since it's a toy example and it gives people the incorrect impression that recursion is slow for the wrong reasons. That example is just a terrible way to compute Fibonacci numbers, but that doesn't mean that using recursion is the problem.

Here is a very fast implementation of Fibonacci numbers using recursion:
#include <iostream>

// M represents a matrix of the form
// (a  b )
// (b a+b)
struct M {
long a, b;

M(long a, long b) : a(a), b(b) {
}
};

M operator*(M x, M y) {
return M(x.a*y.a + x.b*y.b, x.a*y.b + x.b*y.a + x.b*y.b);
}

// Fast exponentiation
M pow(M x, unsigned n) {
if (n==0)
return M(1,0);
if (n==1)
return x;
if (n%2==0)
return pow(x*x,n/2);
if (n%3==0)
return pow(x*x*x,n/3);
return x*pow(x,n-1);
}

// Compute
// (0 1)^n = (fib(n-1)  fib(n) )
// (1 1)    ( fib(n)  fib(n+1))
long fib(unsigned n) {
M m = pow(M(0,1),n);
return m.b;
}

int main() {
std::cout << fib(40) << '\n';
}


Depth-first search is the standard example that should come to mind instead. A recursive implementation is in this case the most natural, it's perfectly fast and small variations of it can be used for many purposes (e.g., to enumerate possibilities in many combinatorial problems, or to play chess).

### #2alvaro

Posted 03 July 2012 - 11:21 AM

I think it is unfortunate that the example of Fibonacci is what most people remember when thinking of recursive functions, since it's a toy example and it gives people the incorrect impression that recursion is slow for the wrong reasons. That example is just a terrible way to compute Fibonacci numbers, but that doesn't mean that using recursion is the problem.

Here is a very fast implementation of Fibonacci numbers using recursion:
#include <iostream>

// M represents a matrix of the form
// (a  b )
// (b a+b)
struct M {
long a, b;

M(long a, long b) : a(a), b(b) {
}
};

M operator*(M x, M y) {
return M(x.a*y.a + x.b*y.b, x.a*y.b + x.b*y.a + x.b*y.b);
}

// Fast exponentiation
M pow(M x, unsigned n) {
if (n==0)
return M(1,0);
if (n==1)
return x;
if (n%2==0)
return pow(x*x,n/2);
if (n%3==0)
return pow(x*x*x,n/3);
return x*pow(x,n-1);
}

// Compute
// (0 1)^n = (fib(n-1)  fib(n) )
// (1 1)  ( fib(n)  fib(n+1))
long fib(unsigned n) {
M m = pow(M(0,1),n);
return m.b;
}

int main() {
std::cout << fib(40) << '\n';
}


Depth-first search is the standard example that should come to mind instead. A recursive implementation is in this case the most natural, it's perfectly fast and small variations of it can be used for many purposes (e.g., to enumerate possibilities in many combinatorial problems, or to play chess).

### #1alvaro

Posted 03 July 2012 - 03:32 AM

I think it is unfortunate that the example of Fibonacci is what most people remember when thinking of recursive functions, since it's a toy example and it gives people the incorrect impression that recursion is slow for the wrong reasons. That example is just a terrible way to compute Fibonacci numbers, but that doesn't mean that using recursion is the problem.

Here is a very fast implementation of Fibonacci numbers using recursion:
#include <iostream>

// M represents a matrix of the form
// (a  b )
// (b a+b)
struct M {
long a, b;

M(long a, long b) : a(a), b(b) {
}
};

M operator*(M x, M y) {
return M(x.a*y.a + x.b*y.b, x.a*y.b + x.b*y.a + x.b*y.b);
}

// Fast exponentiation
M pow(M x, unsigned n) {
if (n==0)
return M(1,0);
if (n==1)
return x;
if (n%2==0)
return pow(x*x,n/2);
if (n%3==0)
return pow(x*x*x,n/3);
return x*pow(x,n-1);
}

// Compute
// (0 1)^n = (fib(n-1)  fib(n) )
// (1 1)	 ( fib(b)  fib(n+1))
long fib(unsigned n) {
M m = pow(M(0,1),n);
return m.b;
}

int main() {
std::cout << fib(40) << '\n';
}


Depth-first search is the standard example that should come to mind instead. A recursive implementation is in this case the most natural, it's perfectly fast and small variations of it can be used for many purposes (e.g., to enumerate possibilities in many combinatorial problems, or to play chess).

PARTNERS