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.
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.
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
- #include <iostream>
- using namespace std;
- int fibonacci(int n)
- {
- if(n==0)
- {
- return 0;
- }
- else if(n==1)
- {
- return 1;
- }
- else
- {
- return (fibonacci(n-1)+fibonacci(n-2));
- }
- }
- int main ()
- {
- cout<<fibonacci(5);
- return 0;
- }
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.
- #include <iostream>
- using namespace std;
- int fib(int m);
- int main()
- {
- int i,n;
- cout<<"Enter the value of n: ";
- cin>>n;
- for(i=1;i<=n;i++)
- {
- cout<<fib(i)<<" ";
- }
- }
- int fib(int m)
- {
- if(m<=2)
- {
- return 1;
- }
- else
- {
- return fib(m-1)+fib(m-2);
- }
- }
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.
