Recursion in C#

Recursion is a programming technique where a method calls itself to solve a problem. In C#, recursion is commonly used to solve problems that can be divided into smaller subproblems of the same type, like calculating factorials, traversing trees, or implementing algorithms like QuickSort.

How Recursion Works

  1. Base Case: The condition where the recursion stops. Without it, the function would call itself infinitely.
  2. Recursive Case: The part of the function where it calls itself with modified arguments.

  3. using System;

  5. class Program
  6. {
  7.     static int Factorial(int n)
  8.     {
  9.         // Base Case: Stop recursion when n is 0
  10.         if (n == 0)
  11.             return 1;
  12.         
  13.         // Recursive Case: Call Factorial with n - 1
  14.         return n * Factorial(n - 1);
  15.     }

  17.     static void Main()
  18.     {
  19.         int number = 5;
  20.         Console.WriteLine($"Factorial of {number} is: {Factorial(number)}");
  21.     }
  22. }

    How It Works:

    • For Factorial(5), the function works as:
      • 5×Factorial(4)5 \times Factorial(4)
      • 4×Factorial(3)4 \times Factorial(3)
      • 3×Factorial(2)3 \times Factorial(2)
      • 2×Factorial(1)2 \times Factorial(1)
      • 1×Factorial(0)=11 \times Factorial(0) = 1
      • Returns 120.

        Types of Recursion

        1. Direct Recursion:

          • The method directly calls itself.

          • void Example() {
          •     Example(); // Direct call
          • }


          • Indirect Recursion:

            • A method calls another method, which in turn calls the first method.

            • void MethodA() {
            •     MethodB();
            • }

            • void MethodB() {
            •     MethodA();
            • }


              Applications of Recursion

              1. Mathematical Problems: Factorials, Fibonacci series.
              2. Data Structures: Tree and graph traversals.
              3. Algorithms: Divide and conquer, backtracking (e.g., Tower of Hanoi).
              4. Sorting: QuickSort, MergeSort.

              Advantages of Recursion

              • Simplifies code for problems with repetitive substructure.
              • Easier to read and write compared to iterative solutions for some problems.

              Disadvantages of Recursion

              • Can be less efficient due to:
                • High memory usage from the call stack.
                • Risk of stack overflow if the recursion depth is too large.
              • Can sometimes be harder to debug.

              Tips for Writing Recursive Functions

              1. Always define a base case to avoid infinite recursion.
              2. Ensure the recursive call moves towards the base case.
              3. Be cautious about the depth of recursion—consider iterative solutions for deeply recursive problems.

              4. using System;

              6. class Program
              7. {
              8.     static int Fibonacci(int n)
              9.     {
              10.         // Base Case
              11.         if (n <= 1)
              12.             return n;

              14.         // Recursive Case
              15.         return Fibonacci(n - 1) + Fibonacci(n - 2);
              16.     }

              18.     static void Main()
              19.     {
              20.         int terms = 7;
              21.         for (int i = 0; i < terms; i++)
              22.         {
              23.             Console.Write($"{Fibonacci(i)} ");
              24.         }
              25.     }
              26. }



Comments

Post a Comment

Popular posts from this blog

Image
In Go, the switch statement is a control structure that allows you to execute one of several code blocks based on the value of an expression. It’s a more efficient and cleaner alternative to using multiple if-else statements, especially when you need to check multiple conditions. Go’s switch statement is powerful and flexible, and it can be used for simple comparisons, type assertions, and even with expressions that return multiple values. Basic Syntax of switch The basic structure of a switch statement in Go is: switch expression { case value1: // Code to execute if expression == value1 case value2: // Code to execute if expression == value2 default : // Code to execute if expression doesn't match any of the cases } Example: package main import "fmt" func main () { day := 3 switch day { case 1 : fmt.Println( "Monday" ) case 2 : fmt.Println( "Tuesday" ) case 3 : fmt.Println(...
Read more
Image
  In Rust, the if statement is used for conditional execution of code. It evaluates a condition, and if the condition is true , the associated block of code is executed. Rust's if statements are versatile and integrate seamlessly with the language's emphasis on safety and expressions. Syntax of if The basic structure of an if statement in Rust is: if condition { // Code to execute if the condition is true } Example: fn main () { let number = 10 ; if number > 5 { println! ( "The number is greater than 5." ); } } if-else Statement You can include an else block to execute code when the condition is false . fn main () { let number = 3 ; if number % 2 == 0 { println! ( "The number is even." ); } else { println! ( "The number is odd." ); } } if-else if Ladder For multiple conditions, you can chain if-else if statements: fn main () { let number = 0 ; if number ...
Read more
Image
  if-else statement helps make decisions in your program. It checks a condition (a true or false statement) and runs code based on whether the condition is true or false. Here’s how it works: If statement : It checks if a condition is true. If the condition is true, the code inside the if block runs. Else statement : If the condition is false, the code inside the else block runs. Example: #include <stdio.h> int main() {     int number = 10;     // Check if number is greater than 5     if (number > 5) {         printf("The number is greater than 5\n");     } else {         printf("The number is 5 or less\n");     }     return 0; } How it works: In this example, the condition is number > 5 . If the number is greater than 5, the program will print "The number is greater than 5". If the number is not greater than 5 (false), the program will print "The number is 5 or less...
Read more