Recursive programs and recursive algorithms part 1

A seminar is going to start. You're sitting in the audience rows. If the whole thing is til and noheer condition. But the speech did not start yet. Suddenly curiosity is to know how many rows in your seat from the first row. But sitting there, counting so many rows, Bowring. Then the way? Very easy, just ask one of your front row ranks in the number of rows. If he says n, then you have your own row (n + 1). So, in front of your request, the next person will sit down and count the rows? Nah! He will just ask the person in front of him, how many numbers are there in the queue. And get the answer and add 1 to her and tell you. In this way the questions will reach to the first row in front of anyone to reach. There is no one else in front of the first-row viewer. So he will not reply to the other person, "I am the number 1 in the row". The person behind him will add 1 to the answer and tell the person behind him. In this way the answers will come from 1 to join you. And you will know your own row number.

Do not do all that work yourself, partly give it to others (where others will do the rest as well as others). Recursive method called this method.

One of the most interesting concepts in computer science is this recursion. But it's not easy to mention before, like the Earth and the ten fun things, the recursion is not easy. There is no computer scientist or programmer who has not been able to learn this idea. So at some point in the text, if something seems to be dull, then there is nothing to be frustrated. If you give some time to the matter, it will be seen that all of them have become clear. It's like riding a bike, or learning to swim. There is no easier way to learn than to stick around.

But do not bother to hear so many warnings at the beginning. Because, we will move in very small steps. And we will discuss the concepts that we need from programming and mathematics from here on the way. Then let's start. Function at the beginning

Function
It is not our intention to discuss how the function's mathematical definition or function idea works in programming language like Java, Java, or how it works. We just want to learn the recursive algorithm through the recursive function. And for this, we will try to see the function in a different way.

At the beginning, I see the mathematical function of a real number,

f (x) = x \ times x ... ... ... (1)

The value or output of this function for x = 5,

f (5) = 5 \ times 5 = 25
Similarly, the value of f (x) can be found for any value of x. Here's the value of the x that we're saying, that's the input. Then the output f is the output f (x) whose value is equal to the square of the input.

There is no such thing as the function's input. We can think of a function whose input is the name of a city. And the output is the city where the city is located. If the name of the function is g then, g (Dhaka) = Bangladesh, g (Paris) = France, etc.

That means, for any function we have to say first, what is its input key Such as the input of any real number, input of any city's name, etc. Just do not have to say the input, if the input is given, then according to the function, the output should be given a rule. This rule can be (1) no mathematical formula like the equation, and a description like g. Even the rules can be written in the form of a computer program or algorithm.

The function's input can be multiple. For example, a function can be made as input of the real numbers x and y,

h (x, y) = \ sqrt {x ^ 2 + y ^ 2} ......... (2)

Those who know Pythagoras' theorem, they have been able to recognize that h function is the length of the x length and the length of the horizontal ligature of a right-angled triangle y.

That means, h is not mathematically written like the equation (2). It can also be written in the form of a form, h is a function that outputs the length of the octave with the length of the two corresponding angles of the right angle of the triangle. When discussing any function, it is very important to describe the function 'what is actually' in its own language.

If we wanted to, we could also publish the function h to f using f. For example,

h (x, y) = \ sqrt {f (x) + f (y)} ......... (3)

Note that (3) and (2) number is the equation but actually doing the same thing. Because, by using (1) we get f (x) = x \ times x and, f (y) = y \ times y, consequently,

h (x, y) = \ sqrt {f (x) + f (y)} = \ sqrt {x \ times x + y \ times y} = \ sqrt {x ^ 2 + y ^ 2} ......... ( 4)

That is, (2) synonymous. The equation (3) A function is mathematically described using the function f.

That means, if you want to calculate the value of a function, other functions can be used. The interesting thing is, not just another function. Some functions may even be used in the description itself. And this type of function is called recursive function.

Recursive function
0, 1, 1, 2, 3, 5, 8, 13, 21, \ ldots
Do you know this trend? Yes it is our very favorite fibonacci section. Apart from the first two, each number of this series is the sum of the previous two numbers. But then where did the first two numbers come from? The mathematician Fibonacchi has actually set out the two numbers to start, and the next number of numbers to be removed from the two previous figures. If we started the series with 0, 1 instead of 3, 4. If I could,

3, 4, 7, 11, 18, 29, \ ldots
Even in this series, all the other numbers except the first one are the sum of the two numbers just before. But I'm going to show that this is not a Fibonacci section.

Use fibonacchi sectionAfter getting two numbers starting with 0 and 1, we can say for the others,

N is the sum of Fibonacci numbers, the sum of n-1 and n-2 is the number of fibonacci numbers.

Mathematically,

F (0) = 0, ......... (5)

F (1) = 1, ......... (6)

And

F (n) = F (n-1) + F (n-2) ......... (7)

(5), (6) and (7), these three equations define the function to find the nth filename number, where F (0) and F (1) are the base steps. And (7) is recursive phase.

Let us see how the 4th digit number can be used by using them.

F (4) = F (3) + F (2) ... .... (8) [(7) using)

= \ {F (2) + F (1) } + \ {F (1) + F (0) } ... ... ... (9) [(8) using the words again (7)

= \ {F (1) + F (0) } + F (1) + F (1) + F (0) ... ... ... (10) [(9) using again (7) on the first position]

= 1 + 0 + 1 + 1 + 0 [[5] and (6) value)

= 3
That is, in recursive step, we define the function itself with its own input for any input. But to ensure that it does not continue forever, we have to fix one or more base steps. Those whose values ​​are offered directly.

Verify yourself

To say a positive factual factorial, we understand that all the numbers of numbers from 1 to the number. That is, being factual of 5, 1 \ times 2 \ times 3 \ times 4 \ times 5. If we name this factual function, then we can write it as fact.
fact (n) = 1 \ times 2 \ times 3 \ times 4 \ times \ ldots \ times n ... ... ... (11)

Now show that recursive equation

fact (1) = 1 ... ... ... ... (12)

fact (n) = n \ times fact (n-1) ... ... (13)

Actually, the function (11) represents the function. Find the value of fact (4), and fact (5), first with the help of equation (11) and then the help of equation (12) and (13).

A function C, with two inputs, is defined in recursive ways in the following ways.
C (n, 0) = 1 ... ... ... (14)

C (n, n) = 1 ... ... ... (15)

C (n, k) = C (n-1, k) + C (n-1, k-1) ......... ... (16)

Here the base case (14), (15) says that if the second input of C is 0 or the input of C is equal to one another, then for that input the value of C is 1. All other types of inputs will be used for summation (16). (14), (15) and (16) use the value of C (4, 2).

[Hint: C (4,2) = C (3, 2) + C (3,1) = ...]

Recession tree
The picture shows how recursion works. To find out the value of F (4) by equation (5), (6) and (7) for that, first write F (4) in a rectangle like Figure 1 (a). This rectangle will tell us node.
From equation (7) we know F (4) is the sum of F (3) and F (2). To illustrate this, we draw two more nodes by staining under F (4) in Figure 1 (b).

Those of whom write F (3) and F (2) respectively. Tell them F (4)'s child node. But we do not know the value of them directly.
So Figure 1 (C) again draws two more child nodes under the node of F (3) and F (2) by using the equation (7). It turns out that this image is now F (1), F (0) wired node. Their values are known from equations (5) and (6).Since they know their value, then, letting them set the values of a breast node under the text node in F (1), F (0) in figure 1 (d). But there is an F (2) node in Figure 1 (c). So under the previous rule, F (1) and F (0) two income-oriented child nodes have been drawn. Those who have been set up in Fig. 1 (e)
Rooted tree is the type of image. The root node of this tree is F (4) from where the tree starts to grow bigger. The node of the node with the node attached to the tree with the spots on the bottom. And the parent of the child is the top node. A parent can have one or more child. There are no children of those nodes who stop at the bottom of the tree and stop there. Leaf node that is such a node. The circular nodes in our figure 1 (e) are the leaf nodes. To be understood, the root node does not have any parent.

The value of each parent node in Fig. 1 (e), the sum of the values ​​of its child node. If the child is in the leaf, then the standard of the leaf is available directly. In this way, the bottom level of the tray is to find the value of its upper level nodes and thus, the value of the root node goes away once it moves in step.

Thus, when the process of determining the value of a recursive function is expressed in the form of a tree, the tree is called a recursion tree. Figure 1 (e) Reconnaissance Tree of F (4) Dham is the name of different parts of this tree, and we are scratched with the rules of making it, because later we will use such a tree to understand the many recursive algorithms.

Verify yourself

The value of function C (n, k) as defined in the equation (14), (15) and (16) is determined by the recursion tree for the value of n = 4 and k = 2 (that is, the value of C (4,2)).
Find out the value of function fact (n) as given in equation (12), (13) n = 5 for the recursion tree.