October 20, 2017 Friday
Bedtime Story
Defining Recursion
We saw last night that factorial function
can be defined in terms of factorials.
This is a classic textbook and even a
bedtime example of recursive behavior.
For a behavior to be recursive it needs to
exhibit the following two properties:
(1) A simple base case that allows to
terminate the operations without resorting to recursion to produce an answer
(in our case it was the fact that factorial of one is one)
(2) A set of rules that reduce all other
cases to the base case
Another mathematical example that exhibits
recursive behavior is the famous Fibonacci sequence where every number after
the first two is the sum of preceding two.
The Fibonacci function can be defined as:
Fn = Fn-1 + Fn-2
A biological example of recursive behavior
is the case of our ancestry.
The base case is that our parents are our
ancestors.
The recursive rule is that the ancestors of
our ancestors are also our ancestors.
Recursion has also been used by many great
artists in their art.
But let us now come to computer science
where recursion is one of its central ideas.
Computer Science sees recursion as a method
or a tool to problem solving wherein the solution to a given problem depends on
the solutions to smaller instances of the same problem.
One must be careful not to mix it up with
something that sounds very similar but in truth is a completely alien concept.
That is iteration.
Iteration is an act of repeating a function
with the output of each repeat becoming the input for the next iteration.
This can either go on endlessly for a fixed
assigned number of times.
Niklaus Wirth (Swiss), the winner of the
1984 Turing Award and the designer of Pascal has to say this about recursion:
“The power of recursion evidently lies in
the possibility of defining an infinite set of objects by a finite statement.
In the same manner, an infinite number of
computations can be described by a finite recursive program, even if this
program contains to explicit repetitions.”
Just to show you what Wirth is meaning to
say, let me write down the factorial function as a recursive function in a
functional programming language like C.
We shall look at the factorial function
programmed in language C in the nights to come.
Stay tuned to the voice of an average story storytelling
chimpanzee or login at http://panarrans.blogspot.com
Good night mon ami and my fellow cousin ape.
Advertisements
Another great educator and a teacher that I am aware of is
Professor Subhashish Chattopadhyay in Bangalore, India.
While I narrate stories, Professor Subhashish an electronic
engineer and a former professor at BARC, does and teaches real mathematics and
physics.
He started the participation of Indian students at the
International Physics Olympiad.
Do visit him here:
All his books can be downloaded for free through this link:
For edutainment and English education of your children, I
recommend this large collection of Halloween Songs for Kids:
No comments:
Post a Comment