possible ways of doing recursion

issacnewton

Hi

I just have some questions on the principle of recursion. We use it to build sequences like Fibonacci etc. In such cases, the recursive rule is additive. So its very simple. But imagine the
problems of constructing the sequences. This comes often in mathematics when the problem asks to prove that such and such sequence exists. There might be problems where recursive
steps can not be written in simple addition of last few terms or using simple mathematical operations. The recursive step might involve complex construction of (n+1)^th
term assuming that n^th term is defined. When recursion is introduced in discrete math books, I see only simple examples. Can you provide examples where complicated steps
are involved in recursive steps in going from n^th term to (n+1)^th
term ? We might talk about the examples outside mathematics, because recursion seems very general idea.

thanks

Stephen Tashi

Recursion is often used in computer programs for the sake of efficiency.

For example, to compute a series of binomial coefficients [itex] \binom{n}{j} [/itex] , it would be inefficient to compute each coefficient individually. It's better to compute [itex] \binom{n}{j+1} [/itex] by multiplying [itex] \binom{n}{j} [/itex] by the appropriate factors.


As another example, to evaluate a polynomial like [itex] 4x^3 + 3x^2 + 6x + 1 [/itex], you wouldn't normally code this as [itex] 4(x)(x)(x) + 3(x)(x) + 6(x) + 1 [/itex]. Instead you would write the code as [itex] x ( x( (4x + 3) + 6) + 1 [/itex]. I suppose that idea could be expressed as a recursion, which you would need to do if your program had a polynomial stored as an array [itex] a_i [/itex] of coefficients and you didn't know the degree of the polynomial in advance.

Consider how the syntax of computer languages is defined recursively.

issacnewton

Stephen, since I am not computer science student, can you point me to the links
explaining how the syntax of computer languages is defined recursively.

I think even prime numbers can be defined in recursive fashion. what do you think ?

Stephen Tashi

http://en.wikipedia.org/wiki/Syntax_diagram

I can't think of any interesting way to do that.

issacnewton

Hi Stephen

here is one way we can manage prime numbers. Base Step: define [itex]x_1 = 2[/itex], since 2 is
divisible by 1 and 2 only, its prime number. Now Inductive Step: Here given [itex]n^{\mbox{th}}[/itex] prime number, we should give the procedure to get [itex](n+1)^{\mbox{th}}[/itex] prime number. Since [itex]n^{\mbox{th}}[/itex] prime number is known, add 1 to it, use divisibility test on it to check if its a prime number. If it turns out to be prime number then its fine, we found our next prime number. If not add 1 again to this number and repeat the procedure. And so we can find the [itex](n+1)^{\mbox{th}}[/itex] prime number in such manner. Is something wrong in using recursion this way ?

Stephen Tashi

I wouldn't say that is wrong, but it is definitely not interesting. It doesn't use use recursion in any essential way since the test for divisibility by smaller primes is the crucial point. The recursive definition, as far as I can see, doesn't provide any insight into the results of that test.

issacnewton

here is the way I understand recursion. after the base step is defined, we assume that
n th term satisfying the required criteria exists. and then we set out to give a procedure to produce (n+1) th term. so we can put some black box between the n th term and (n+1) th term ( for the purpose of explanation I am using simple recursion) and we can put some
valid algorithm in that black box...... I don't know if this is the view of mathematicians...

chiro

Hey isaacnewton.

If you are talking about generating a sequence based on prior values then the most general form is going to look something like f_n+1(X) = a series of functions based on compositions of functions of the form f_a() in which an expansion can be made to generate some kind of algebraic representation for f_n+1 in terms of some initial conditions specified in X (remember X might be an initial vector rather than just a scalar).

Usually what happens in mathematics is that general problems get put into classes and then the classes get studied in their right more or less independently until they are well understood to move on to a higher level of abstraction or to consider other classes in conjunction with the initial class.

This page might give an idea of some of these classes and where to go from there.

http://en.wikipedia.org/wiki/Recurrence_relation

issacnewton

thanks chiro for chipping in

I remember a game kids used to play in my college. They will organise some 10-11 teams of about 3 persons in each team. And each team is given a piece of paper which says where
to go next (we can call this base step). Once the team reaches that particular place, they will
get some kind of reward (maybe chocolates) and again they will find a new piece of paper
explaining whats the next task. The next task may involve solving some mathematical puzzle and the puzzle will give the clue to go to the next place. When they go to the next place, again they are asked to do some task and then they get directions to go to the next place. And so on. So here we have a base step initially. Without that initial chit of paper the team doesn't know what to do. After that they just have to complete the given task and they are given the directions for new place. So this kind of serves as an inductive step. You are probably familiar with this game, I think boy scouts do that too. Well my point is, recursion can be defined in a very general way like this. I think computer networks probably use some kind of recursion like this...