Recursion and Recursive function

What is recursion!

Hi! Guys,how are you all? Today's post I'm gonna tell you what is recursion and also recursive function.So if you just completed your begginer level and starting to solve mid-level programming it might be useful and better understandable  for you.When I was new to the word recursion or recursive function I just google it.What I see in my search list I was surprised! See the image below

Is it a mistake! Nope,you will understand it after reading this post.

According to wikipedia  "Recursion is the process by which something is defined in terms of itself or its type"

Check the below images.

Now you may find some clue what I'm talking about! Recursion!

Better if I gave you some realistic example of recursion.Have you ever been a saloon or a parlor.I'm saying you this because they had mirrored room with opposite stand.So one mirror reflects to another mirror.If you look at any of this mirror you will visualize a wonderfull recursion.

Recursive Function

In terms of computer languages recursion means that a function can call itself.

Normally main function can call another function or a function but in terms of recursion a function call itself.

Before start explaining I would like to share with you something that is similar  to recursive function.Did you guys  watched 2010 released Christopher Nolan's movie inception? Where casted Leo DiCaprio as Dom Cob who is a thief can extract information from people mind using dreams.Cob and his associates architects dream into dream.

So how they came into reality! well, using kick.
Kick means something destructive happening in a dream or in their mind to wake up.
All I'm saying you to you this because recursive function has similar functionalities like inception.It can call itself like dreams in a dream,in dream, And what is the kick of recursive function? Well it has base case or halting case or you can say arguments which terminate the loop avoid becoming an infinite loop.Without base case your function will be a paradox recursion.

Again Function

Before starting coding let's do some math.Let's define function of a real number 

If the input of the function is x=5 the output will be 

Similarly we can find  any value of this function just putting the value of x=6,7,8,9....

Although the input of a function can't always be a number .It can be anything like imagine a function where we input a city name the output will be the country

ex.(Dhaka)=Bangladesh

     g(Paris)=France

That means for any function first of all we have to declare what will be the input, Like f's input was a number and g's input was a city and according to the input we have to describe what will be the output like it's a  number or a city.

We can describe it as a mathematical formula or may be writing a program or may be a algorithm.

A function can have many inputs.A function h is defined by two real numbers x and y

So folk if you're familiar with Pythagoras theorem you already known that x is the adjacent and y is the opposite of a right angle  where h represent the hypotenuse 

So guys if we want we can represent h using f

ex.

If you're smart enough you already known that 3 and 2 both equations are doing same things using 1 we find 

So we find

which is similar to the equation (2).In equation (3) the function h defined by function f.

So we are clear that to find one function value we can use another function.But the interesting thing a function can defined itself.This kind of function we called recursive function.

Look at the sequence below

0,1,1,1,3,8,13,21........

Is it familiar to you!Yup this is our favourite fibonacci sequence.Fibonacci was a mathematician who describe the series the next number is found by adding up the two numbers before it.

We find the third number of the Fibonacci sequence 0+1=1

and like all the Fibonacci number we find the 9th Fibonacci number is 21=8+31

so we can find the nth position Fibonacci number is

F(n)=F(n-1)+F(n-2)

If you're clever enough you will see we already made a recursive function.So here F(n) is a recursive function because it is defined by its own.

Lets print 5th position Fibonacci number using recursive function

1.  
2. #include <iostream>
3. 
   
4. using namespace std;
5. 
   
6. int fibonacci(int n)
7. {
8.     if(n==0)
9.     {
10.         return 0;
11.     }
12.     else if(n==1)
13.     {
14.         return 1;
15.     }
16.     else
17.     {
18.         return (fibonacci(n-1)+fibonacci(n-2));
19.     }
20. }
21. int main ()
22. {
23.     cout<<fibonacci(5);
24.     return 0;
25. }

Output:5

If you're not clear how this recursive function work you can see the below recursion tree.

I will give you another example.Your task is find out how it work.

2. #include <iostream>
3. 
   
4. using namespace std;
5. 
   
6. int fib(int m);
7. 
   
8. int main()
9. {
10.     int i,n;
11.     cout<<"Enter the value of n: ";
12.     cin>>n;
13.     for(i=1;i<=n;i++)
14.     {
15.         cout<<fib(i)<<" ";
16.     }
17. }
18. int fib(int m)
19. {
20.     if(m<=2)
21.     {
22.     return 1;
23.     }
24. 
    
25.     else
26.     {
27.         return fib(m-1)+fib(m-2);
28.     }
29. }

Some programming languages have no loop ex. for loop,while loop, they use pure recursion.

Lisp,Eel,OCaml etc.Which don't have iterative or looping,So they represent iteration using recursive function.