Scribd
Upload
2 views

Recursion

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until a base condition is met. The document explains the basic structure of recursive functions, types of recursion (direct and indirect), and provides examples including factorial calculation and Fibonacci sequence. It also highlights the importance of base cases, common mistakes, and suggests practice problems for further understanding.

Uploaded by

hasibshahriar04
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
2 views

Recursion

Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until a base condition is met. The document explains the basic structure of recursive functions, types of recursion (direct and indirect), and provides examples including factorial calculation and Fibonacci sequence. It also highlights the importance of base cases, common mistakes, and suggests practice problems for further understanding.

Uploaded by

hasibshahriar04
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Recursion

Recursion is a programming technique where a function calls itself to solve smaller


instances of a problem until a base condition is met.
Base Case: The condition that stops the recursion.
Recursive Case: The part where the function calls itself with modified parameters.
Basic Structure of Recursive Functions:
type function_name (args)
{
// function statements
// base condition
// recursion case (recursive call)
}

When a recursive function is called:


• Each call adds a new frame to the call stack.
• When the base case is reached, the stack starts unwinding.
• Each function call completes its execution and returns its result.
#include<bits/stdc++.h>
using namespace std;

int factorial(int n)
{
if (n == 0) // Base case
return 1;
return n * factorial(n - 1); // Recursive case
}

int main()
{
cout << "Factorial of 5: " << factorial(5) << endl;
return 0;
}

factorial(5)→factorial(4)→factorial(3)→factorial(2)→factorial(1)→factorial(0)

120 = 5*24 ← 4*6 ← 3*2 ← 2*1 ← 1*1 ← 1

Page 1 of 4
Types of Recursion

1. Direct Recursion: A function calls itself directly.


• Head Recursion: The recursive call happens before processing the current logic.
#include<bits/stdc++.h>
using namespace std;

void headRecursion(int n)
{
if (n == 0) // Base case
return;
headRecursion(n - 1); // Recursive call before processing
cout << n << " "; // Process after recursion
}

int main()
{
cout << "Head Recursion: ";
headRecursion(5); // Output: 1 2 3 4 5
return 0;
}

• Tail Recursion: The recursive call happens after processing the current logic.
#include<bits/stdc++.h>
using namespace std;

void tailRecursion(int n)
{
if (n == 0) // Base case
return;
cout << n << " "; // Process before recursion
tailRecursion(n - 1); // Recursive call after processing
}

int main()
{
cout << "Tail Recursion: ";
tailRecursion(5); // Output: 5 4 3 2 1
return 0;
}

Page 2 of 4
• Tree Recursion: A function makes multiple recursive calls, creating a tree-like
structure of calls.
#include<bits/stdc++.h>
using namespace std;

int treeRecursion(int n)
{
if (n <= 1) // Base case
return n;
return treeRecursion(n - 1) + treeRecursion(n - 2); // Two recursive calls
}

int main()
{
cout << "Tree Recursion: Fibonacci sequence\n";
for (int i = 0; i < 6; i++)
{
cout << "Fib(" << i << ") = " << treeRecursion(i) << endl;
}
return 0;
}

2. Indirect Recursion: A function calls another function, which in turn calls the original
function.
#include<bits/stdc++.h>
using namespace std;

void functionA(int n);


void functionB(int n);

void functionA(int n)
{
if (n <= 0) // Base case
return;
cout << "A: " << n << endl;
functionB(n - 1); // Calls functionB
}

void functionB(int n)
{
if (n <= 0) // Base case

Page 3 of 4
return;
cout << "B: " << n << endl;
functionA(n / 2); // Calls functionA
}

int main()
{
cout << "Indirect Recursion:\n";
functionA(10); // Starts the recursion
return 0;
}

➢ Base Case is Critical. Without it, the function will recurse infinitely, leading to a
stack overflow.
➢ Recursive solutions can be memory-intensive due to the call stack. Tail recursion
can mitigate this in some languages.
➢ When to Use Recursion: Problems that can be divided into smaller subproblems,
like: Factorials, Fibonacci sequence, Tree traversals (binary trees), Divide-and-
conquer algorithms (Merge Sort, Quick Sort).
➢ Common Mistakes: Missing Base Case(Leads to infinite recursion), Incorrect State
Update(not reducing the problem size in each recursive step), Overlapping
Subproblems(Can be optimized using memoization or dynamic programming)

Practice Problems

1. Write a program to find the sum of the elements of an array using recursion.
2. Implement recursive binary search.

Page 4 of 4

You might also like