RUSSIAN DOLL AND RECURSION TECHNIQUE

There is one Russian wooden doll. A large doll. If you open the head, a less large doll is found inside. If you take out the second doll and open it, another small doll appears. If you open the third doll, another smaller one is found. This goes on up to seven or eight dolls.

Suppose, you want to do some 'operation' with the dolls. That is, you want to label each doll. Take out all the dolls one by one. Fix the label on the smallest one and put it inside doll which slightly bigger. Label the second doll and repeat the operations till you label the biggest one.

This operation is laborious to do. But we can write the command for the operation concisely as given below.

Do
"label the doll and also label the doll inside"
Repeat
until no doll is found.

There is a computer algorithm by name 'Recursion' similar to this concept.

Suppose, you want to sum the natural numbers from 1 to N. You can write the command as follows.

Define sum(N) = 1+2+......+N
Hence we can write the computer command as:

sum(N)= N+ sum (N-1) if N is not equal to 0

When the computer encounters this command, it will magically sum the 1 to N numbers. Let us see how it works.

Key word sum appears both sides. Hence the statement will refer itself again and again.

Let N=10
So sum(10)= 10 +sum (10-1)
but sum (10-1)= sum(9)

The computer will interpret the sum(9) as
sum(9)= 9+sum (9-1)
Because of back-reference in the sum(N) command

This will go on till N=0. Now the computer has stripped down sum(10) command and reached the innermost command sum(1) . Next the computer will execute the commands from sum(1) to sum(10) (from bottom up) and get you the sum 55 That is it, you are the master and the computer is the slave.

Recursion algorithm saves lot of memory space and speed up the execution.

The recursion can be applied to factorial, searching. find GCD, construct fractals etc.

Recursion is the important technique in the computer programming.

Comments

LISSAJOUS FIGURES

Definition: "When a particle is subjected to two sine wave motion or two oscillatory motion at right angles, the particle describes lissajous figures". We know sine wave motion and circular motion is basically same. Hence we draw two circles A and B perpendicular to each other. The circle B rotates twice faster than circle A. That is, frequency of circle B is two times than that of A. A particle at the intersection of two circles is subjected to two sine wave motion A and B at 90 degree simultaneously. The particle will describe figures depending on the frequency and phase of A and B . In our case, the ratio of frequency is 1:2 and the two waves are in phase. To draw lissajous figures : A moving point in both the circles are chosen. Here we should remember; during the time taken by the circle A to complete one rotation, circle B completes two. Hence the points are marked on the circles according to their speed. Then straight lines

THE PARABOLA

A jet of water shooting from a hose pipe will follow a parabolic path. What is the so special about parabola. Y= x^2 Draw a graph for the above equation. It will result in a parabola. This parabola is also called unit parabola. Any equation involving square will yield a parabola. Example: Y = 2x^2 +3x+3 (also called quadratic equation) X= 2 and -2, both satisfies the equation 4 = X^2. Parabolic equations always have two solutions. Any motion taking place freely under gravity follows parabolic path. Examples: An object dropped from a moving train, A bomb dropped from flying plane, A ball kicked upwards. If a beam of light rays fall on the parabolic shaped mirror, they will be reflected and brought to focus on a point. This fact is made use of in Dish Antenna, Telescope mirrors, etc. Inverted parabola shape is used in the construction of buildings and bridges. Because the shape is able to bear more weight. A plane

CASINO'S GAME

Let us find out how the casino survives with mathematics. Say, your friend invite you for a game of dice. You must bet (wager) 2 dollars. If you roll 'six' you will get back 8 dollars. The game will go on for 30 rounds. All sounds good. The probability of rolling 'six' is 1/6. Since the game will be played for 30 times, the 'expected win' is 30*1/6 = 5. That is, you are expected to win 5 rounds out of 30. Hence your gain will be 5 * 8 =40 dollars. ok. This also implies that you will loose 25 rounds. Hence your loss will be 25*2 =50 dollars. Your net gain will be gain-less = 40-50 = -10 dollars. For 30 rounds, the loss is -10 dollars, Hence, for one round =-10/30 = -1/3 dollars. There will be a loss of -1/3 or 0.33 dollars per round. It is not a fair game. Let us make a simple formula to calculate 'Pay out per round\. The probability for a win = p The pay-out in case of win = V No. of rounds = n The expect

sciencecapsules

Search This Blog