Yes, factorials can be defined through recursion. But so can multiplication of non-negative integers:
def mult(a, b):
if a == 0 or b == 0: return 0
if a == 1: return b
return mult(a-1, b) + b
>>> mult(5, 9)
45
> the simplest (AFAIK) recurrence relationship ...that can be produced.
The positive integers is even easier. For n >= 0:
F(0) = 0
F(n) = 1 + F(n-1)
Another interesting thing about the Fibonnaci Sequence is that it has a closed-form solution, given in your OEIS link as:
F(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n*sqrt(5))
It is also non-polynomial. In the limit, it approaches a simple exponential.
Nor is it bounded by a polynomial, meaning that if you pick any positive integer p and any constant C, and define g(n) = C n^p then for a large enough n you will find that |g(n)| < |F(n)| .
Furthermore, A000435 , with its n^n - like form, grow even faster than exponential. It's similar to factorial growth.
> as a fellow Mathematician
I am not a mathematician. Neither are you.
> s to figure out when/where/why the number table / difference table / triangle / fan -- fails -- between the simplest of all recurrence relationship formula, the Fibonnaci sequence -- and this one
Consider f(n) = f(n-1) + 1 where f(0) = 0. This is the sequence 0, 1, 2, 3, .... This addition of 1 can be seen trivially in the difference table.
Consider f(n) = f(n-1) + f(n-1) with f(1) = 1. This is the sequence 1, 2, 4, 8, 16, 32, or 2^n, which is an exponential function.
Consider the Fibonacci function f(n) = f(n-1) + f(n-2) with f(1) = f(2) = 1. This uses an addition of the two previous numbers. It approaches an exponential function as n gets larger.
Consider f(n) = n * f(n-1) with f(1) = 1 This is the factorial. It grows faster than the exponential function.
Because the last one uses a multiplication instead of addition, a difference table (which is based on subtraction) won't show the pattern. The inverse of multiplication is division, so use a division table.
> deeply recursive algorithms
These are not deeply recursive. For an example of those, see the Ackermann function. https://en.wikipedia.org/wiki/Ackermann_function , which is not primitive recursive like functions we've discussed so far.