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

Your heart -you do not know

Size and Location: The human heart is roughly the size of a clenched fist and is located slightly to the left of the center of the chest. Despite its relatively small size, the heart plays a crucial role in pumping blood throughout the entire body. Heartbeat Variability: The heart does not beat at a constant rate. The interval between heartbeats can vary, and this variability is considered a sign of a healthy heart. Factors such as breathing, emotions, and physical activity influence the heartbeat. Electrical Conduction: The heart's contractions are controlled by electrical impulses. The sinoatrial (SA) node, often called the "natural pacemaker," generates electrical signals that regulate the heartbeat and coordinate the pumping of blood. Blood Pumping Capacity: On average, the human heart pumps about 2,000 gallons (or 7,570 liters) of blood each day. Over a lifetime, this amounts to pumping enough blood to fill several Olympic-sized swimming pools. Heart Chambers and V...

THE WORK HORSE "="

One cannot think of a mathematical step without 'is equal to ' . It balances right hand side and left hand side. It aids simplification and manipulation of a mathematical expression. example: 2(A+B) = C 2A+2B = C 2A = C-2B A = C-2B/ 2 In an electronic calculator, the pressing of ' = " sign executes an asthmatic expression or simply calculates. In computer languages, it plays very important role. A = B When a computer looks at this expression, the value stored in the location named B is just transferred to the storage named A . After execution both A and B will have the same value an...

THE EARTH, A SUPER ORGANISM

JOIN MY COURSE: "Become a programmer in a day with python" A man called 'love lock' (what a name) proposed a theory called Gaia theory, named after Greek Goddess. It says, "Earth is a self-regulating organism like a human being. The organic life in it interacts with in-organic matter and maintains atmosphere, temperature and environment". Hence the earth is still suitable for the life to thrive. Imagine, in a particular place, there are lot of flowers. Some flowers are white and some are darkly coloured. We know, white reflects light and heat while dark absorbs the same. White flowers can thrive in hot climate. But dark flowers requires cold climate. The absorption and reflection balances and the environment reaches average, warm temperature at which both the flowers can co-exist. This is the essence of "Gaia" theory. On our earth, ...

sciencecapsules

Search This Blog