Possible ways of doing recursion

• issacnewton
In summary, recursion is often used in computer programs for the sake of efficiency. However, it can be difficult to write recursive steps in a simple way, and complex steps can sometimes be involved.
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 nth 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 nth term to (n+1)th
term ? We might talk about the examples outside mathematics, because recursion seems very general idea.

thanks

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

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

As another example, to evaluate a polynomial like $4x^3 + 3x^2 + 6x + 1$, you wouldn't normally code this as $4(x)(x)(x) + 3(x)(x) + 6(x) + 1$. Instead you would write the code as $x ( x( (4x + 3) + 6) + 1$. 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 $a_i$ of coefficients and you didn't know the degree of the polynomial in advance.

IssacNewton said:
We might talk about the examples outside mathematics, because recursion seems very general idea.

Consider how the syntax of computer languages is defined recursively.

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 ?

IssacNewton said:
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.
http://en.wikipedia.org/wiki/Syntax_diagram

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

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

Hi Stephen

here is one way we can manage prime numbers. Base Step: define $x_1 = 2$, since 2 is
divisible by 1 and 2 only, its prime number. Now Inductive Step: Here given $n^{\mbox{th}}$ prime number, we should give the procedure to get $(n+1)^{\mbox{th}}$ prime number. Since $n^{\mbox{th}}$ 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 $(n+1)^{\mbox{th}}$ prime number in such manner. Is something wrong in using recursion this way ?

IssacNewton said:
Is something wrong in using recursion this way ?

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.

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

IssacNewton said:
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 nth 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 nth term to (n+1)th
term ? We might talk about the examples outside mathematics, because recursion seems very general idea.

thanks

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

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 what's 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...

1. What is recursion and how does it work?

Recursion is a programming technique where a function calls itself repeatedly until a certain condition is met. It works by breaking down a complex problem into smaller, simpler versions of itself until a base case is reached.

2. What are the advantages of using recursion?

Recursion allows for efficient and elegant solutions to certain problems, especially those that involve repetitive tasks. It also helps in reducing code complexity and makes it easier to read and understand.

3. What is the difference between linear and binary recursion?

Linear recursion is where a function calls itself only once, while binary recursion involves two recursive calls within the function. Binary recursion is commonly used in divide and conquer algorithms.

4. What are some common pitfalls of using recursion?

One common pitfall is that if a base case is not reached, the function will continue to call itself indefinitely, leading to an infinite loop. Another pitfall is the potential for stack overflow if the recursive calls are too deep.

5. How can I determine when to use recursion in my code?

Recursion is best suited for problems that can be broken down into smaller sub-problems of the same type. It is also useful for tasks that require repetitive or iterative processes. However, it may not always be the most efficient solution, so it is important to consider other approaches as well.

Replies
18
Views
2K
Replies
1
Views
1K
Replies
4
Views
2K
Replies
11
Views
1K
Replies
1
Views
5K
Replies
16
Views
2K
Replies
11
Views
4K
Replies
11
Views
1K
Replies
2
Views
2K
Replies
4
Views
1K