Recursion, not as simple as it seems

Many things may seem trivial at the start, but may actually have deep interesting results.


One of the stunning example is the Game of Life, created by John Conway.
"Death by isolation"
"Death by overcrowding"
"Birth by companionship"
Simple rules, that can be understood by closely everyone, actually has more than it meets the eye.

Having not only the fact that the game is unpredictable, it also strikes at the behavior of humanity.

Although as a game, it has limited applications.
Similarly, recursion also run by simple rules.

"Functions calling itself"
It indeed seems simple.
At first glance, it may seem that the coder is too lazy to write the duplicate codes inside another separate function.
Instead, he decided to call the function itself.

Seems trivial. In fact, it seems to be bad practice to be lazy to such degree.
At first glance.

Of course.
First impressions may be deceiving.

Given a recursive definition, is there always an analytical solution?

How is the natural numbers defined?
Do we say 1 + 1 = 2, because we generalize by our everyday interaction?
Surely, it would seem so, yet it is not.

Certainly, almost nobody deal with addition of gigantic numbers daily,
yet how did we come up with the answer to:
perhaps 1 million + 1 million?

It wouldn't seem likely that we can GENERALIZE this result by our interaction with the environment.

Surely not.

One way is to define the natural number, as a recursive structure.

We define 1 + 1 to be the number 2.
We add 1 onto 2:
 2 + 1
to create the next number in the sequence.
Thus, to attain the number 1 million, we would need to start the recursive definition,
to show the result of 1 million + 1 million.
If there was not the invention of arithmatic, would there be any other way to solve the problem?

Perhaps.

Yet there are problems upon recursive structures that are unable to be solved analytically.
If that is true, then what are we left with?

Perhaps, only the recursive definition itself.

Thus, we must work with the definition, somehow.
This is the important result of recursive function, being able to use the recursive definition
to its advantage.

Consider the Fibonacci sequence
Is there an analytical solution to the Fibonacci sequence?
Perhaps.

Is it trivial to attain? Very much so.

This is because of the very nature of Fibonacci sequence being a recursive structure.
In order to attain the next number in the sequence, the definition requires the previous ones to
be attained already.

Thus, if we pick an arbitrary point in the sequence, we would be unable to use the definition at all.
Since, we have not been able to attain the previous numbers.

Then, how would we be able to calculate, perhaps
the 1 million-th number of the Fibonacci sequence?

Perhaps, we could use the recursive definition to our advantage.
 Take the first 2 fibonacci numbers.
Start the recursive definition.
Repeat the definition for a set amount of time.
We would be able to attain our answer.

This seems decidedly trivial, since we have the tool of recursive functions at our disposal
which takes advantage of the recursive structure itself when attaining the solution.

If there was no analytical solution, then would we just give up on solving the problem?
Surely not.
We have the recursive formula at our disposal, and to attain the result, we are more than welcome
to use it.

The fact that recursion can solve problems that are unable to be solved otherwise is already
an indicator of its importance.
Yet from the beginning, it is not clear from the rule of recursion:
"functions calling itself"
would have profound applications.

It is indeed not as simple as the rule suggests, and given an arbitrary problem,
if there are recursive definition, then, perhaps
we are better off using the recursion to our advantage.

Xiao