Recursion in C++

Recursion in C++

Here, in this page we will discuss the concept of recursion in C++ .  A function that calls itself is known as a recursive function. And, this technique is known as recursion. When the function will call itself then that call is known as recursive call.
The recursion continues until some condition is met. To terminate the process of recursion, it is necessary that recursive function contains a base condition. • It makes the length of code shorter.
• Makes code more cleaner.
• It is especially good for working on things that have many possible branches and are too complex for an iterative approach.
• Recursion is best suited in trees and graphs problems.

• Recursive programs takes a lot of stack space compared to an iterative program.
• They uses more processor time.
• It is more difficult to debug a recursive code as compared to an equivalent iterative program.

Why Stack Overflow error occurs in recursion?

If the base case is not reached or not defined, then the stack overflow problem may arise.

Let’s Discuss the program to find N-th fibonacci number using recursion. To understand the concept of recursion clearly.

Algorithm :

• Declare a function say fib(int n)
• Base condition will be if(n<=1) return 1
• Otherwise return fib(n-1)+fib(n-2) Code to find N-th fibonacci number using recursion in C++

#include<bits/stdc++.h>
using namespace std;

//Recursive function
int fib(int n){

if(n<=1) return 1; // Base condition

return fib(n-1)+fib(n-2);
}

//Driver Code
int main(){

int n = 4;
cout<<n<<"-th fibonacci number is "<<fib(n);
}
Output :

4-th Fibonacci number is 5