5.1 Principle of recursion

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. It is based on the principle of dividing a problem into smaller subproblems of the same type. The recursive approach consists of two main components:

Base Case: This is the condition under which the recursion stops. It prevents infinite recursion by providing a simple case that can be solved without further recursion.
Recursive Case: This is where the function calls itself with a smaller or simpler input, moving towards the base case. The recursive case breaks the problem into smaller subproblems.

How Recursion Works

Function Call Stack: Each recursive call creates a new layer in the call stack. When the base case is reached, the function returns a value to the previous call, unwinding the stack.
Stack Overflow: If there are too many recursive calls without reaching the base case, it can lead to a stack overflow error due to limited stack space.

Example of Recursion

A classic example of recursion is calculating the factorial of a number $n$ :

Factorial Definition

Base Case: $factorial(0)=1\text{factorial}(0) = 1$
Recursive Case: $factorial(n)=n×factorial(n−1)\text{factorial}(n) = n \times \text{factorial}(n – 1)$

C Implementation

Here’s a simple C program that demonstrates recursion through the factorial function:

#include <stdio.h>

// Function to calculate factorial recursively
int factorial(int n) {
// Base case
if (n == 0) {
return 1;
}
// Recursive case
return n * factorial(n – 1);
}

int main() {
int number;
printf(“Enter a positive integer: “);
scanf(“%d”, &number);

if (number < 0) {
printf(“Factorial is not defined for negative numbers.\n”);
} else {
printf(“Factorial of %d = %d\n”, number, factorial(number));
}

return 0;
}

5.2 Comparison between recursion and iteration

Recursion and iteration are both fundamental techniques used to solve problems and perform repeated tasks in programming. Each approach has its advantages and disadvantages. Here’s a detailed comparison:

Aspect	Recursion	Iteration
Definition	A function calls itself to solve smaller subproblems.	A loop repeats a block of code until a condition is met.
Syntax	Typically involves function calls and base/recursive cases.	Uses looping constructs like `for`, `while`, and `do-while`.
State Management	Each recursive call maintains its own state.	A single state is maintained in the loop.
Memory Usage	Uses more memory due to the call stack.	Generally uses less memory as it operates in a single frame.
Performance	May be slower due to overhead from multiple function calls.	Usually faster as there’s no overhead from function calls.
Termination	Requires a base case to terminate recursion.	Terminates when the loop condition becomes false.
Readability	Can be more readable and easier to understand for problems that fit the recursive model.	May become complex for problems that have a natural recursive structure.
Debugging	Harder to debug due to multiple function calls.	Easier to debug since all logic is contained in a single loop.
Use Cases	Suitable for problems involving trees, graphs, or problems naturally defined recursively (e.g., factorial, Fibonacci).	Preferred for straightforward repetitive tasks and when performance is critical.

Example Comparison

Let’s consider the example of calculating the factorial of a number using both recursion and iteration.

Recursive Implementation

#include <stdio.h>

// Recursive function to calculate factorial
int factorial_recursive(int n) {
if (n == 0) {
return 1; // Base case
}
return n * factorial_recursive(n – 1); // Recursive case
}

Iterative Implementation

#include <stdio.h>

// Iterative function to calculate factorial
int factorial_iterative(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i; // Multiply result by i
}
return result;
}

5.3 Common Recursive Problems: Factorial, Fibonacci Sequence, GCD, and Tower of Hanoi

Here’s an overview of four classic recursive problems, along with their definitions, recursive algorithms, and explanations.

1. Factorial

Definition: The factorial of a non-negative integer $n$ is the product of all positive integers less than or equal to $n$ . It is denoted by $n!$ .

Recursive Formula:

Base Case: $0! = 1$
Recursive Case: $\times (n-1)!$

C Implementation:

#include <stdio.h>

// Recursive function to calculate factorial
int factorial(int n) {
if (n == 0) {
return 1; // Base case
}
return n * factorial(n – 1); // Recursive case
}

int main() {
int number;
printf(“Enter a non-negative integer: “);
scanf(“%d”, &number);
printf(“Factorial of %d = %d\n”, number, factorial(number));
return 0;
}

2. Fibonacci Sequence

Definition: The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence is: 0, 1, 1, 2, 3, 5, 8, 13, …

Recursive Formula:

Base Cases: $F (0) = 0$ , $F (1) = 1$
Recursive Case: $F (n) = F (n - 1) + F (n - 2)$

C Implementation:

#include <stdio.h>

// Recursive function to calculate Fibonacci
int fibonacci(int n) {
if (n == 0) {
return 0; // Base case
} else if (n == 1) {
return 1; // Base case
}
return fibonacci(n – 1) + fibonacci(n – 2); // Recursive case
}

int main() {
int n;
printf(“Enter a non-negative integer: “);
scanf(“%d”, &n);
printf(“Fibonacci of %d = %d\n”, n, fibonacci(n));
return 0;
}

3. Greatest Common Divisor (GCD)

Definition: The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder.

Euclidean Algorithm:

Base Case: If $b = 0$ , then $GCD(a,b)=a\text{GCD}(a, b) = a$
Recursive Case: $b)\text{GCD}(a, b) = \text{GCD}(b, a \mod b)$

C Implementation:

#include <stdio.h>

// Recursive function to calculate GCD
int gcd(int a, int b) {
if (b == 0) {
return a; // Base case
}
return gcd(b, a % b); // Recursive case
}

int main() {
int a, b;
printf(“Enter two non-negative integers: “);
scanf(“%d %d”, &a, &b);
printf(“GCD of %d and %d = %d\n”, a, b, gcd(a, b));
return 0;
}

4. Tower of Hanoi

Definition: The Tower of Hanoi is a classic puzzle that involves moving a stack of disks from one peg to another, using a third peg as an auxiliary. The rules are:

Only one disk can be moved at a time.
A disk can only be placed on top of a larger disk or an empty peg.

Recursive Algorithm:

Move $n - 1$ disks from source peg to auxiliary peg.
Move the nth disk from source peg to destination peg.
Move $n - 1$ disks from auxiliary peg to destination peg.

C Implementation:

#include <stdio.h>

// Recursive function to solve Tower of Hanoi
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
if (n == 1) {
printf(“Move disk 1 from %c to %c\n”, source, destination); // Base case
return;
}
towerOfHanoi(n – 1, source, auxiliary, destination); // Step 1
printf(“Move disk %d from %c to %c\n”, n, source, destination); // Step 2
towerOfHanoi(n – 1, auxiliary, destination, source); // Step 3
}

int main() {
int n;
printf(“Enter the number of disks: “);
scanf(“%d”, &n);
printf(“Solution for Tower of Hanoi with %d disks:\n”, n);
towerOfHanoi(n, ‘A’, ‘C’, ‘B’); // A, B, and C are the names of rods
return 0;
}

5.4 Applications and Efficiency of recursion

Recursion is a powerful programming technique that has a wide range of applications in computer science and software development. Below are some common applications of recursion, along with an analysis of its efficiency.

Applications of Recursion

Mathematical Computations:
- Factorial Calculation: Used to calculate the factorial of a number.
- Fibonacci Sequence: Generates Fibonacci numbers recursively.
- Greatest Common Divisor (GCD): Efficiently finds GCD using the Euclidean algorithm.
Sorting Algorithms:
- Quicksort: A recursive sorting algorithm that divides the array into smaller subarrays based on a pivot element.
- Mergesort: A divide-and-conquer algorithm that recursively sorts and merges subarrays.
Tree and Graph Traversal:
- Depth-First Search (DFS): Used in trees and graphs to explore nodes recursively.
- Binary Tree Traversal: Inorder, Preorder, and Postorder traversals can be implemented using recursion.
Backtracking Algorithms:
- N-Queens Problem: Places N queens on a chessboard such that no two queens threaten each other.
- Sudoku Solver: Solves Sudoku puzzles using recursive backtracking.
Dynamic Programming:
- Many dynamic programming problems can be solved using a recursive approach with memoization to optimize overlapping subproblems, such as the Knapsack problem and matrix chain multiplication.
Fractal Generation:
- Recursion is used in algorithms to generate fractals like the Mandelbrot set and Sierpinski triangle.
Game Theory:
- Used in algorithms for solving games like Tic-Tac-Toe and Chess, where recursion helps evaluate possible moves.

Efficiency of Recursion

Time Complexity

The time complexity of a recursive algorithm depends on the number of recursive calls and the amount of work done in each call.
For example, the naive recursive approach for calculating Fibonacci numbers has exponential time complexity $O(2^n)$ due to overlapping subproblems, while a dynamic programming approach reduces it to $O (n)$ .

Space Complexity

Recursive algorithms can consume more memory due to the call stack:
- Each recursive call adds a new frame to the call stack, consuming stack memory.
- In the worst case, the space complexity can be $O (n)$ , where $n$ is the depth of the recursion.

Stack Overflow

Recursive algorithms are subject to stack overflow errors if the recursion depth exceeds the maximum stack size, especially for deep recursive calls (e.g., calculating Fibonacci numbers without memoization).

Optimization Techniques

Tail Recursion:
- A recursive function is tail-recursive if the recursive call is the last operation in the function. Some languages optimize tail recursion to reduce stack usage, effectively transforming it into iteration.
Memoization:
- Caches results of expensive function calls and returns the cached result when the same inputs occur again. This is particularly useful for overlapping subproblems (e.g., in Fibonacci calculations).
Iterative Solutions:
- In cases where recursion can lead to inefficiency or stack overflow, converting a recursive solution to an iterative one can improve performance and reduce memory usage.

Write a program to solve the problem of TOH

Here’s a complete C program to solve the Tower of Hanoi (TOH) problem. The program demonstrates how to move a set of disks from one rod to another while adhering to the rules of the game.

Tower of Hanoi Program in C

#include <stdio.h>

// Recursive function to solve Tower of Hanoi
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
// Base case: if there is only one disk
if (n == 1) {
printf(“Move disk 1 from rod %c to rod %c\n”, source, destination);
return;
}

// Move n-1 disks from source to auxiliary rod
towerOfHanoi(n – 1, source, auxiliary, destination);

// Move the nth disk from source to destination rod
printf(“Move disk %d from rod %c to rod %c\n”, n, source, destination);

// Move the n-1 disks from auxiliary to destination rod
towerOfHanoi(n – 1, auxiliary, destination, source);
}

int main() {
int n; // Number of disks
printf(“Enter the number of disks: “);
scanf(“%d”, &n);

printf(“The sequence of moves involved in Tower of Hanoi are:\n”);
towerOfHanoi(n, ‘A’, ‘C’, ‘B’); // A, B, and C are the names of rods
return 0;
}

Explanation of the Program

Function towerOfHanoi:
- Parameters:
  - n: The number of disks to move.
  - source: The rod from which to move the disks.
  - destination: The rod to which the disks are to be moved.
  - auxiliary: The auxiliary rod used for moving disks.
- Base Case: If there’s only one disk, move it directly from the source to the destination.
- Recursive Case:
  - Move $n - 1$ disks from the source rod to the auxiliary rod.
  - Move the $n$ th disk from the source rod to the destination rod.
  - Move the $n - 1$ disks from the auxiliary rod to the destination rod.
Main Function:
- Prompts the user to enter the number of disks.
- Calls the towerOfHanoi function to execute the solution.

Running the Program

Compile the Program: Use a C compiler like gcc:

gcc tower_of_hanoi.c -o tower_of_hanoi
Run the Compiled Program:

./tower_of_hanoi
Input: Enter the number of disks when prompted.

Example Output

If you enter 3 for the number of disks, the output will be:

The sequence of moves involved in Tower of Hanoi are:
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C

This output shows the steps required to move the disks according to the rules of the Tower of Hanoi problem. Each line indicates a move of a disk from one rod to another.

Write a program to print Fibonacci series

Here’s a simple C program that prints the Fibonacci series up to a specified number of terms. The program allows the user to input how many terms of the Fibonacci series they want to generate.

Fibonacci Series Program in C

#include <stdio.h>

int main() {
int n, i; // Number of terms and loop variable
int first = 0, second = 1, next; // First two terms of the Fibonacci series

// Ask the user for the number of terms
printf(“Enter the number of terms in the Fibonacci series: “);
scanf(“%d”, &n);

// Check for valid input
if (n <= 0) {
printf(“Please enter a positive integer.\n”);
return 1;
}

printf(“Fibonacci Series: \n”);

// Print the Fibonacci series
for (i = 1; i <= n; i++) {
if (i == 1) {
printf(“%d “, first); // Print the first term
continue;
}
if (i == 2) {
printf(“%d “, second); // Print the second term
continue;
}
next = first + second; // Calculate the next term
first = second; // Update the first term
second = next; // Update the second term
printf(“%d “, next); // Print the next term
}

printf(“\n”); // New line for better output formatting
return 0;
}

Explanation of the Program

Variables:
- n: Number of terms in the Fibonacci series that the user wants.
- first: Holds the value of the first term (initially 0).
- second: Holds the value of the second term (initially 1).
- next: Used to calculate the next term in the series.
Input:
- The user is prompted to enter the number of terms in the Fibonacci series.
Output:
- The program checks if the input is a positive integer.
- It uses a loop to calculate and print the Fibonacci series up to the specified number of terms.
- The first two terms are printed directly, and subsequent terms are calculated by adding the previous two terms.

Running the Program

Compile the Program: Use a C compiler like gcc:

gcc fibonacci.c -o fibonacci
Run the Compiled Program:

./fibonacci
Input: Enter the number of terms you want in the Fibonacci series when prompted.

Example Output

If you enter 10, the output will be:

Fibonacci Series:
0 1 1 2 3 5 8 13 21 34

This output represents the first 10 terms of the Fibonacci series.

Here’s a simple C program that calculates the factorial of a given non-negative integer using both an iterative and a recursive approach. The program prompts the user to enter a number and then displays its factorial.

Factorial Program in C

#include <stdio.h>

// Function to calculate factorial using recursion
unsigned long long factorial_recursive(int n) {
if (n == 0 || n == 1) // Base case
return 1;
else
return n * factorial_recursive(n – 1); // Recursive case
}

// Function to calculate factorial using iteration
unsigned long long factorial_iterative(int n) {
unsigned long long result = 1; // To hold the factorial result
for (int i = 2; i <= n; i++) {
result *= i; // Multiply result by each number
}
return result;
}

int main() {
int n; // Variable to hold user input

// Prompt user for input
printf(“Enter a non-negative integer: “);
scanf(“%d”, &n);

// Check for valid input
if (n < 0) {
printf(“Factorial is not defined for negative integers.\n”);
return 1; // Exit if input is invalid
}

// Calculate factorial using both methods
unsigned long long fact_recursive = factorial_recursive(n);
unsigned long long fact_iterative = factorial_iterative(n);

// Display the results
printf(“Factorial of %d (Recursive): %llu\n”, n, fact_recursive);
printf(“Factorial of %d (Iterative): %llu\n”, n, fact_iterative);

return 0;
}

Explanation of the Program

Functions:
- factorial_recursive: This function calculates the factorial using recursion. It checks for the base case (0! and 1! both return 1) and calls itself with $n - 1$ until it reaches the base case.
- factorial_iterative: This function calculates the factorial using an iterative approach with a loop. It multiplies numbers from 2 to $n$ .
Main Function:
- Prompts the user to enter a non-negative integer.
- Validates the input to ensure it’s non-negative.
- Calls both the recursive and iterative functions to calculate the factorial and stores the results.
- Displays the calculated factorials.

Running the Program

Compile the Program: Use a C compiler like gcc:

gcc factorial.c -o factorial
Run the Compiled Program:

./factorial
Input: Enter a non-negative integer when prompted.

Example Output

If you enter 5, the output will be:

Enter a non-negative integer: 5
Factorial of 5 (Recursive): 120
Factorial of 5 (Iterative): 120

This output indicates that the factorial of 5 is 120, calculated using both the recursive and iterative methods.

Write a program to calculate gcd of two numbers

Here’s a simple C program that calculates the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm. This program allows the user to input two integers and then computes their GCD.

GCD Program in C

#include <stdio.h>

// Function to calculate GCD using the Euclidean algorithm
int gcd(int a, int b) {
// Continue until b becomes 0
while (b != 0) {
int temp = b; // Store b in a temporary variable
b = a % b; // Update b to be the remainder of a divided by b
a = temp; // Update a to be the previous value of b
}
return a; // The GCD is now in a
}

int main() {
int num1, num2; // Variables to hold the two numbers

// Prompt the user for input
printf(“Enter two positive integers: “);
scanf(“%d %d”, &num1, &num2);

// Check for valid input
if (num1 <= 0 || num2 <= 0) {
printf(“Please enter positive integers only.\n”);
return 1; // Exit if input is invalid
}

// Calculate GCD
int result = gcd(num1, num2);

// Display the result
printf(“The GCD of %d and %d is: %d\n”, num1, num2, result);

return 0;
}

Explanation of the Program

Function gcd:
- Takes two integers $a$ and $b$ .
- Uses the Euclidean algorithm to find the GCD by repeatedly replacing $a$ with $b$ and $b$ with $\mod b$ until $b$ becomes 0.
- Returns $a$ , which will be the GCD.
Main Function:
- Prompts the user to enter two positive integers.
- Validates the input to ensure the integers are positive.
- Calls the gcd function to compute the GCD and stores the result.
- Displays the GCD of the two numbers.

Running the Program

Compile the Program: Use a C compiler like gcc:

gcc gcd.c -o gcd
Run the Compiled Program:

./gcd
Input: Enter two positive integers when prompted.

Example Output

If you enter 48 and 18, the output will be:

Enter two positive integers: 48 18
The GCD of 48 and 18 is: 6

This output indicates that the GCD of 48 and 18 is 6.

Previous Chapter Next Chapter

Important Questions

Comments

Discussion

You must login to submit your discussion. Click here to login.

0 Comments

Loading . . .