Recursion function and Fibonacci series

Recursive Function: A recursive function is a function that calls itself, either directly, or indirectly. Recursion is an important topic in upper-level computer science courses.

• A recursive function invokes itself.
• A recurrence relation is a relation that is specified using itself.
• Anything that can be done recursively can be done iteratively and vice versa.
• If there were a data processing Inquisition programmers would probably be burned at the stake based on a belief or disbelief in recursion.

Advantages:

1. Code to implement an algorithm can be very succinct.
2. If an algorithm is specified recursively, in the form of a recurrence
   relation, it is the easiest way to code it.

Disadvantages:

1. Expensive in CPU time and memory.

Recurrence Relation Example:

n! = n * (n-1) * (n-2).....1 = n * (n-1)!

4! = 4 * 3 * 2 * 1 = 24

Recursive Function Example:

A translation of the recurrence relation into C++.

int RcrsFact(int Num)

{

if (Num == 0) return 1;

else return (Num * RcrsFact(Num - 1));

}

Example using recursion: Fibonacci Numbers

Fibonacci
a. Real Name: Leonardo of Pisa
b. Fibona cci sh ort for: Filius Bon Acci, or good son of Acci.
c. Well traveled merchant with extensive acquaintance with Mideast
d. Familiar with Arabian mathematics.
e. Introduced European world to Arabic notations for numerals (as
opposed to Roman numerals) in his book Liber Abaci.


Fibonacci Sequence: Fibon(n) = Fibon(n-1) + Fibon(n-2)
a. Number of leaves on certain plants (assuming that no leaves fall
off) is a Fibonacci number.
b. Fibonacci numbers appear in odd places in series or solutions to
equations.
c. Doubly recursive.

Recursive Logic:

int RcrsFibon(int Num)

{

if (Num == 0) return 0;

else if (Num == 1) return 1;

else if (Num == 2) return 1;

else return (RcrsFibon(Num - 1) + RcrsFibon(Num - 2));

}