Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to teach myself mathematics. I only started last year with a previous knowledge of basic arithmetic. I often make a detour into regions featuring problems that are a bit too deep for me. I'm often too curious to wait until I was able to catch up on the necessary bedding. I hope you'll excuse me :-)

Wolfram|Alpha says:

$$f(x) = f(x-1)*b \to f(x) = c_1 b^{x-1}$$

This is how I would compute the original recursive algorithm(?):

$$f(x) = f(x-1)*b$$

$$\begin{align} \\ f(4) &= f(4-1)*b \\ &= f(f(3-1)*b)*b \\ &= f(f(f(2-1)*b)*b)*b \\ &= f(f(f(f(1-1)*b)*b)*b)*b \\ &= \qquad ... \end{align}$$

But how do I compute the recurrence relation $f(x) = c_1 b^{x-1}$?

I would compute the Fibonacci numbers like this:

$$\begin{align} F_n &= F_{n-1} + F_{n-2}\\ F_0 &= 0\\ F_1 &= 1\\ F_5 &= F_{5-1} + F_{5-2}\\ &= F_4 + F_3\\ &= (F_3 + F_2) + (F_2 + F_1)\\ &= ((F_2 + F_1) + (F_1 + F_0)) + ((F_1 + F_0) + F_1)\\ &= (((F_1 + F_0) + F_1) + (F_1 + F_0)) + ((F_1 + F_0) + F_1) \\ &= 5 \end{align}$$

I'm also not sure about the difference between a recursive algorithm and its recurrence relation. I'd be grateful if someone could enlighten me or simply link me up.

share|improve this question
add comment

2 Answers

I believe that your way to compute $f(n)$ is not correct, as you have outlined in the question. Observe that $f(4) = b * f(3) = b^2 * f(2)$ and not $f(4) = b * f(f(2)*b)$.

That said, you have $$f(n) = b * f(n-1) = b^2 * f(n-2) = \ldots = b^{n-1} * f(1).$$ Say that your initial condition states that $f(1) = c_1$, you can conclude that $f(n) = c_1 * b^{n-1}$.

share|improve this answer
add comment

A recurrence relation defines a function depending on its values on points of lower "rank". Since you want to be able to calculate the function, you also need some bases cases that are just given (like axioms). For example, the recurrence relation defining the Fibonacci numbers defines $F_n$ in terms of $F_{n-1},F_{n-2}$; the base cases $F_1=1,F_0=0$ are not defined in terms of previous elements.

We can have more complicated definitions of "rank". Here are two examples. One can define the binomial coefficients using Pascal's identity $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ with appropriate bases cases. Written out, that would be $$C(n,k) = C(n-1,k-1) + C(n-1,k), \quad C(0,k) = 1_{k=0}.$$ So in that cases $(n-1,\cdot)$ is of lower rank than $(n,\cdot)$.

Another example is the determinant - it's a function on $n \times n$ matrices (arrays of numbers) which is defined as the single value in case $n=1$, and using some formula involving $(n-1)\times(n-1)$ matrices otherwise.

In general, for the definition to work, the notation of rank must be a well ordering.


A recursive algorithm is a procedure which calls itself. For example, you can use the following pseudocode to calculate the Fibonacci numbers:

if ((n == 0) || (n==1)) return n;
else return F(n-1) + F(n-2);

Every recurrence relation can be computed this way. In this particular case, the algorithm for calculating $F_n$ runs in exponential time (in other words, it's very inefficient), and there are better ways to calculate $F_n$; for example, you could calculate the values iteratively:

F[0] = 0; F[1] = 1;
for (int i = 2; i <= n; i++) F[i] = F[i-1] + F[i-2];

There are even better algorithms.

Conversely, recursive algorithms have other uses, for example the best algorithms for sorting a list of numbers are recursive and use the "divide and conquer" paradigm.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.