Author: saqibkhan

Recursion is a programming technique where a function calls itself over again and again with modified arguments until it reaches its base case, where the recursion stops.

It breaks a problem down into smaller, more manageable sub-problems, recursion allows for elegant and better solutions to complex problems.

Recursive Function

A recursive function is a function which is particularly used for recursion where a function calls itself, either directly or indirectly, to address a problem. It must include at least one base case to terminate the recursion and one recursive case where the function invokes itself.

• Base Case − It’s a case where recursion stops or ends after reaching that particular condition.
• Recursive Case − It’s a case where a function calls itself over again with decremented value until and unless it reaches its base case.

Creating a Recursive Function

The following syntax is used to implement a recursive function in C++ −

function name(param_1, param_2..){<base condition><function body><return statement>}

Here,

• Where, function name(param_1, param_2..) is a function declared as “name” passing with multiple parameters in it as per requirement.
• Now the function body is being divided into three sub-categories : base condition, function body and return statement.
• In base condition we will define its base case, where recursion has to stop or end.
• In the function body, a recursive case will be defined, where we need to call the function over again and again as per requirement.
• At last, the return statement will return the final output of the function.

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

Calling a Recursive Function

Calling a recursive function is just like calling any other function, where you will use the function’s name and provide the necessary parameters in int main() body.

To call a recursive function, use the following syntax −

func_name(value);

Example of Recursion

Below is an example of a recursion function in C++. Here, we are calculating the factorial of a number using the recursion −

#include <iostream>usingnamespace std;// Recursive Function to Calculate Factorialintfactorial(int num){// Base caseif(num <=1){return1;}// Recursive caseelse{return num *factorial(num -1);}}intmain(){int positive_number;
   cout <<"Enter a positive integer: ";
   cin >> positive_number;if(positive_number <0){
  cout &lt;&lt;"Wrong Input, Factorial is not Defined for Negative Integer"&lt;&lt; endl;}else{
  cout &lt;&lt;"Factorial of "&lt;&lt; positive_number &lt;&lt;" is "&lt;&lt;factorial(positive_number)&lt;&lt; endl;}return0;}</code></pre>


Output



Enter a positive integer: 4 (input)
Factorial of 4 is 24




Explanation



If take input int positive_number as 4, It will send integer to function name 'factorial' as factorial(4)



Initial Call: factorial(4)



This function will check base case (n<=1), as it’s not satisfying the base case, therefore move forward to recursive case and will compute as "4 * factorial(3)".



Second call: factorial(3)



This function will again check base case, as it’s not satisfying it, therefor will again move forward to recursive case , and compute as "3 * factorial(2)".



Third Call: factorial(2)



Checks base case and computes "2 * factorial(1)"



Fourth call: factorial(1)



Checks base case, now since function satisfying this base case condition that’s less than or equal to 1, So it will return 1.



Unwinding the Stack



Now, the recursive calls will start returning: After the 4th call now it will again start from back, returning to the Third Call first.



Return to Third Call: factorial(2)



We already have factorial(1) = 1, therefor factorial(2) will return, "2 * factorial(1)", that’s "2 * 1" , which returns as factorial(2) equals to 2.



Return to Second Call: factorial(3)



Now, factorial(2) is 2, therefore factorial(3) equals to "3 * 2", that’s 6.



Return to Initial Call: factorial(4)



We have factoria(3) which returns 6, therefore, factorial(4) returns "4 * 6 = 24".



Types of Recursion



Recursion can be categorized into two main types where each with its own sub-categories −



1. Direct Recursion



Direct recursion occurs when a function calls itself directly −



Simple Direct Recursion



The function calls itself with a simpler or smaller instance of the problem. It is used for solving problems like factorial calculation, fibonacci sequence generation, etc.



Tail Recursion



A form of direct recursion where the recursive call is the last operation in the function. It is used for solving accumulative calculations and list processing problems.



intfactorial(int n,int result =1){if(n <=1){return result;}else{returnfactorial(n -1, n * result);// Tail recursive call}}



Head Recursion



The recursive call is made before any other operation in the function. Processing occurs after the recursive call returns. It is used for tree traversals and output generation.



voidprintNumbers(int n){if(n >0){printNumbers(n -1);// Recursive call first
  cout &lt;&lt; n &lt;&lt;" ";// Processing after recursive call}}</code></pre>


Linear Recursion



Each function call generates exactly one recursive call, forming a linear chain of calls. It is used for simple counting or summing.



intlinearRecursion(int n){if(n <=0){return0;}else{returnlinearRecursion(n -1)+1;// Linear recursive call}}



2. Indirect Recursion



Indirect recursion occurs when a function calls another function, which eventually leads to the original function being called. This involves two or more functions calling each other.



Mutual Recursion



In mutual recursion, two or more functions call each other in a recursive manner, forming a cyclic dependency. It is used for even and odd number classification and grammar parsing.



Open Compiler



#include <iostream>usingnamespace std;voideven(int n);voidodd(int n);voideven(int n){if(n ==0){
  cout &lt;&lt;"Even"&lt;&lt; endl;}else{odd(n -1);// Calls odd}}voidodd(int n){if(n ==0){
  cout &lt;&lt;"Odd"&lt;&lt; endl;}else{even(n -1);// Calls even}}intmain(){even(4);// Outputs: Evenodd(5);// Outputs: Oddreturn0;}</code></pre>


Output



Even
Even




Nested Recursion



The nested recursion is a form of indirect recursion where a recursive function makes another recursive call inside its own recursive call. It is used for solving complex mathematical and algorithmic problems.



Open Compiler



#include <iostream>usingnamespace std;intnestedRecursion(int n){if(n >100){return n -10;}else{returnnestedRecursion(nestedRecursion(n +11));// Nested recursive calls}}intmain(){
   cout <<nestedRecursion(95)<< endl;// Outputs: 105return0;}



Output



91




Advantages of Recursion




Simplicity and reduced boilerplate code − Recursion helps to simplify solving problems which have a built-in recursive structure, like working with trees or solving combinatorial problems by making it easier to understand and implement.



Backtracking − Recursion is a great fit for backtracking algorithms, which involve examining all possible solutions to find one which meets certain criteria.



Effective solutions for divide-and-conquer problems − Recursion works perfectly for Divide-and-conquer algorithms, where problems are broken down into smaller sub parts and are solved one by one. This makes problem solving more efficient and easy.




Recursion Vs. Iteration



Recursion is a method where a function calls itself over again and again with modified arguments until it reaches its base case which stops the recursion. Whereas, an iteration involves using loops (such as for, while or do-while) where it involves repeatedly executing blocks of code until a certain condition is met.



Recursion or Iteration: When to Use?



Recursion




The problems which can be divided into similar sub-problems or which have natural recursive patterns such as tree traversal or combinational tasks and manageable depth.



When a user needs simple, cleaner and readable code as it provides clean proper arranged code.



Examples: Tree and graph traversals, divide-and-conquer algorithms like quicksort and mergesort, and problems involving backtracking like solving mazes or puzzles.




Iteration




Iterative solutions are generally more efficient in terms of memory and execution time and which involves simple repetition.



For the problems which require simple looping because iteration is usually more straightforward and efficient.



Iteration is more stable for problems which require a large number of repetitions, as it doesn't risk stack overflow.



Examples: Looping of Array, Vectors and lists, where require simple mathematical computation and repeated execution of a block of code.




Comparison between Recursion and Iteration



Recursion
Iteration
Time Complexity
It can be greater because of its repeated function calls nature.
Comparatively less.
Space Complexity
Recursion often uses more Memory because of the call stack.
Uses a fixed amount of Memory.
Code Size
In the recursion, the code size is smaller.
Comparatively larger code size.
Execution Speed
The execution speed is slow when you use recursion.
Execution speed is more.



Limitations of Recursion



The following are limitations of recursion −




Memory Consumption − Each recursive call adds a new frame to the call stack, which can consume a significant amount of memory.



Stack Overflow Risk − As recursion relies on call stack to manage function calls, Deep recursion can lead to stack overflow as it exceeds the stack size limit.



Performance Overhead − Recursive functions can be less efficient than iterative ones because they involve overhead from multiple function calls and managing the call stack, which can significantly impact performance, especially with deep recursion.



Debugging Complexity − Debugging Recursive code can be challenging, especially when dealing with complex recursion or large recursion depths. It needs careful handling of base cases and logic.



Space Complexity − Due to the call stack in recursion, it can lead to consuming a lot of memory.

C++ multiple function parameters describe the ability of a function to accept more than one argument or can say functions with multiple parameters to perform operations using several inputs, this feature makes a function to execute more complex operations by working with multiple subset of data at once.

Syntax

In C++, you can define a function with multiple parameters by listing them in the function’s declaration and definition, separated by commas. Here’s the basic syntax −

return_type function_name(param1_type param1_name, param2_type parame2_name,...);

Where,

param1_type and param1_name are parameter type (eg. int, char, bool, string) and its name respectively, similarly param2_type (eg. int, char, bool, string) and param2_name are parameter type and its name respectively and so on.

Data Types for Multiple Function Parameters

There are 2 types of passing data to multiple function parameters, as given in the following −

1. Single Data Type for Multiple Parameters

Functions where all parameters are of the same data type.

Example

Open Compiler

#include <iostream>usingnamespace std;// Function taking multiple parameters or arguments of same data type (int)voidsum(int a,int b,int c){
   cout <<"Sum: "<<(a + b + c)<< endl;}intmain(){sum(1,2,3);return0;}

Output

Sum: 6

2. Multiple Data Types for Multiple Parameters

Functions where parameters can have different data types.

Example

Open Compiler

#include <iostream>usingnamespace std;// Function taking arguments of different data typesvoidgetInfo(string name,int age,double height){
   cout << name <<" is "<< age <<" years old and "<< height <<" meters tall."<< endl;}intmain(){getInfo("Aman",26,1.78);getInfo("Naman",32,1.65);return0;}

Output

Aman is 26 years old and 1.78 meters tall.
Naman is 32 years old and 1.65 meters tall.

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

Multiple Parameters Passing Techniques

Multiple parameters (or, single) passing techniques in C++ refer to the methods which are used to pass arguments to functions. These techniques define how the data is transferred and manipulated within the function. Here we will discuss few primary techniques −

1. Pass by Value

In pass by value, a copy of the actual parameter’s value is passed to the function. The changes made to the parameter inside the function do not affect the original argument. It is safe and straightforward but can be inefficient for large data structures due to copying.

2. Pass by Reference

This method passes a reference to the actual parameter, allowing the function to modify the original argument. The function works with the original data rather than a copy. It is efficient as it avoids copying, but requires careful handling to avoid unintended modifications.

3. Mutable vs Immutable Types

Mutable Types	Immutable Types
These are types whose instances can be modified after they are created.	These are types whose instances cannot be changed after they are created.
Lists, dictionaries, and sets are common mutable types.	Integers, strings, and tuples are common immutable types.

Types of Multiple Function Parameters

In C++, functions are capable of accepting multiple parameters, and these parameters can be categorized in various ways. Here’s a breakdown for different types of multiple function parameters in C++ −

1. Fixed Number of Parameters

A function with a fixed number of parameters where it has a specific and unchanging number of input parameters.

Example

Open Compiler

#include <iostream>usingnamespace std;// Function with a fixed number of argumentsvoidgetDetails(int age,double height,const string& name){
   cout <<"Name: "<< name <<", Age: "<< age <<", Height: "<< height << endl;}intmain(){getDetails(25,5.6,"Sam");return0;}

Output

Name: Sam, Age: 25, Height: 5.6

2. Variable Number of Parameters

A function that can accept a variable number of parameters or arguments. This is typically implemented using variadic functions or template parameter packs.

Example

Open Compiler

#include <iostream>usingnamespace std;// Variadic template functiontemplate<typename... Args>voidprintNumbers(Args... args){(cout <<...<< args)<< endl;}intmain(){printNumbers(1,2,3);// Outputs: 123printNumbers(4,5,6,7,8);// Outputs: 45678return0;}

Output

123
45678

3. Default Parameters

The default parameters are the parameters with default values that can be omitted when calling the function. The function uses the default values if no arguments are provided for those parameters.

Example

Open Compiler

#include <iostream>usingnamespace std;// Function with default parametersvoidgreet(const string& name ="Guest",int age =0){
   cout <<"Hello, "<< name;if(age >0){
  cout &lt;&lt;". You are "&lt;&lt; age &lt;&lt;" years old.";}
   cout << endl;}intmain(){greet();// Outputs: Hello, Guestgreet("Alice");// Outputs: Hello, Alicegreet("Bob",30);// Outputs: Hello, Bob. You are 30 years old.return0;}

Output

Hello, Guest
Hello, Alice
Hello, Bob. You are 30 years old.

4. Named Parameters (C++ Specific)

Though C++ does not support named parameters directly, you can achieve similar functionality using a class or struct to encapsulate parameters.

Example

Open Compiler

#include <iostream>usingnamespace std;// Structure to encapsulate parametersstructPerson{
   string name;int age;double height;};// Function that takes a parameter objectvoidprintPerson(const Person& p){
   cout <<"Name: "<< p.name <<", Age: "<< p.age <<", Height: "<< p.height << endl;}intmain(){
   Person alice ={"Alice",25,5.9};printPerson(alice);return0;}

Output

Name: Alice, Age: 25, Height: 5.9

5. Parameter Objects

A single parameter that is a complex type like a class or struct, encapsulating multiple related values.

Example

Open Compiler

#include <iostream>usingnamespace std;// Class to hold multiple parametersclassRectangle{public:int width;int height;Rectangle(int w,int h):width(w),height(h){}};// Function that takes a parameter objectvoidcalculateArea(const Rectangle& rect){
   cout <<"Area: "<<(rect.width * rect.height)<< endl;}intmain(){
   Rectangle rect(10,5);calculateArea(rect);// Outputs: Area: 50return0;}

Output

Area: 50