Chapter 5: Recursion Notes, Polytechnic 3rd semester computer programming notes

Hello Everyone, Welcome back to Rajasthan Polytechnic BTER. This is Garima Kanwar Welcome you all to Rajasthan Polytechnic BTER at where you will get notes of rajasthan polytechnic 1st semester, acnd cs branch 3rd and 5th semester.

In todays post you will get polytechnic 3rd semester Computer Programming Notes of Chapter 5: Recursion. so Let's start.

 Recursion is a powerful programming technique where a function calls itself to solve a problem. It is particularly useful for problems that can be broken down into smaller, more manageable sub-problems.

5.1 Introduction to Recursion

A recursive function is defined in terms of itself, meaning it can call itself to perform its task. Recursion consists of two main components:

• Base Case: The condition under which the recursion stops. It prevents infinite recursion and provides a solution for the simplest instance of the problem.
• Recursive Case: The part of the function that includes the recursive call. It reduces the problem into smaller sub-problems.

Example of a Simple Recursive Function: Factorial The factorial of a non-negative integer $n$ is the product of all positive integers up to $n$. It can be defined recursively as:

• $\text{factorial}(n) = n \times \text{factorial}(n - 1)$ for $n > 0$
• $\text{factorial}(0) = 1$ (base case)

C Implementation:

"C"
#include <stdio.h>

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

int main() {
    int number = 5;
    printf("Factorial of %d is %d\n", number, factorial(number)); // Output: 120
    return 0;
}

5.2 Recursive Solutions

Recursive solutions are often used for problems that can naturally be divided into smaller instances of the same problem, such as:

• Fibonacci Series: Each number in the series is the sum of the two preceding ones.

  • Recursive Definition:
    • $\text{fibonacci}(n) = \text{fibonacci}(n - 1) + \text{fibonacci}(n - 2)$ for $n > 1$
    • $\text{fibonacci}(0) = 0$
    • $\text{fibonacci}(1) = 1$

  C Implementation:

  "C"
  #include <stdio.h>
  
  int fibonacci(int n) {
      if (n == 0) return 0; // Base case
      else if (n == 1) return 1; // Base case
      else return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
  }
  
  int main() {
      int n = 5;
      printf("Fibonacci of %d is %d\n", n, fibonacci(n)); // Output: 5
      return 0;
  }
  

• Tower of Hanoi: A classic problem that involves moving disks from one rod to another, following specific rules.

  Recursive Solution:

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

  C Implementation:

  "C"
  #include <stdio.h>
  
  void towerOfHanoi(int n, char source, char destination, char auxiliary) {
      if (n == 1) {
          printf("Move disk 1 from %c to %c\n", source, destination);
          return;
      }
      towerOfHanoi(n - 1, source, auxiliary, destination);
      printf("Move disk %d from %c to %c\n", n, source, destination);
      towerOfHanoi(n - 1, auxiliary, destination, source);
  }
  
  int main() {
      int n = 3; // Number of disks
      towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
      return 0;
  }
  

Advantages of Recursion:

• Simplifies code and makes it easier to read and maintain.
• Natural solution for problems that exhibit overlapping subproblems and optimal substructure.

Disadvantages of Recursion:

• Overhead of multiple function calls can lead to increased memory usage and slower execution time.
• Risk of stack overflow if the recursion depth is too high.

---

This blog post is written by Garima Kanwar, and the blog name is 'Rajasthan Polytechnic BTER.' We hope this post has provided you with a clear understanding of recursion and its applications. For more such detailed notes, please visit 'Rajasthan Polytechnic BTER' regularly.

If you want any other subject notes or any other study material please let me know in Comment Section.