Register to reply 
Possible ways of doing recursionby issacnewton
Tags: recursion 
Share this thread: 
#1
Mar612, 05:08 PM

P: 610

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 


#2
Mar712, 09:30 AM

Sci Advisor
P: 3,295

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. 


#3
Mar712, 04:43 PM

P: 610

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 ? 


#4
Mar812, 08:40 AM

Sci Advisor
P: 3,295

Possible ways of doing recursion



#5
Mar812, 10:17 PM

P: 610

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 ? 


#6
Mar912, 12:22 AM

Sci Advisor
P: 3,295




#7
Mar912, 12:40 AM

P: 610

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... 


#8
Mar912, 12:50 AM

P: 4,573

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 


#9
Mar912, 01:25 AM

P: 610

thanks chiro for chipping in
I remember a game kids used to play in my college. They will organise some 1011 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... 


Register to reply 
Related Discussions  
Recursion in C  Programming & Computer Science  12  
Which Fibonacci number would you like me to compute  Programming & Computer Science  19  
Function is F(n) = n(n+1)  General Math  4  
Illogicways to sucker people/ways to avoid being a sucker  General Discussion  1  
What is the largest number of pieces you can get by cutting a pizza  Introductory Physics Homework  1 