CsitLabs
  • CSIT Labs
  • 1st Semester
    • Digital Logics
      • Lab 1
      • Lab 2
      • Lab 3
      • Lab 4
      • Lab 5
      • Lab6
    • IIT
    • Physics Lab Report Formet
  • 2nd Semester
    • Algorithms used in Discrete Structure class
    • Microprocessor
      • 8085 Microprocessor
        • Arithmetic and Logical Instruction Set
        • Branching Instruction Set
        • Data Transfer and Instruction Set
        • Multiply, Divide and Memory Block Operations
        • Rotate Instruction Set
        • Subroutine, Stack and BCD Conversion](Subroutine_Stack_BCD_Conversion
      • 8086 Microprocessor
        • Basic Arithmetic
        • Practice Programs for 8086 Microprocessor
        • String Processing
    • Object Oriented Programming using C++
      • File Access Pointers
      • Standard Exceptions in C++
    • Statistics-I
  • 3rd Semester
    • Computer Architecture
      • Practical labs
    • Computer Graphics
      • Practial
      • Simulation of Two Dimensional Transformation
      • Scan Conversion Algorithm
    • Data Structures and Algorithms
      • Array methods (Introduction)
      • Stack
      • Queue
      • Recursion
      • Linked List
      • Sorting Algorithms
      • Searching and Hashing Algorithms
      • Trees and Graphs
      • Lab practice
    • Numerical Method Labs
      • Lab practice
    • Statistics-II Labs
      • Confidence interval of mean assuming normal distribution
      • One Sample T test
      • Two Sample T test
      • Regression Analysis
      • Two Sample T test
      • Design_of_Experiment
        • CRD (Completely Randomized Design)
        • RBD (Randomized Block Design)
        • RBD (Randomized Block Design)
      • Non-parametric_test
        • Binomial Test
        • Cochran Q test
        • Kolmogorov-Smirnov one sample test
        • Run test
        • Friedman-F_test
          • Friedman F test
          • Friedman F test
        • Kruskal-Wallis-H_test
          • Kruskal Wallis H test
          • Kruskal Wallis H test
        • Mann-Whitney-U_test
          • Mann Whitney U test
          • Mann Whitney U test
        • Median_test
          • Median Test
          • Median Test
        • Wilcoxon-Matched-pair_signed_rank_test
          • Wilcoxon Matched pair signed rank test
          • Wilcoxon Matched pair signed rank test
  • 4th Semester
    • Artificial Intelligence
    • Computer Networks
      • Networking commands in CMD
    • DBMS Lab
    • Operating System
      • Linux Commands
    • Theory of Computation
      • Lab 1 (DFA)
      • Lab 2 (NFA)
  • 5th Semester
    • Cryptography
    • Design and Analysis of algorithms
    • Multimedia
      • Animation Creation with Blender
      • FL Studio - Simple Effect Creation
      • Macromedia FreeHand - Logo Creation
      • Audio Mixing
      • Adobe Photoshop - ID Card Creation
      • Video Editing with Adobe Premiere Pro
    • Simulation & Modeling
      • Lab 1: Random Number Generation
    • System Analysis and Design
    • Web Technology
      • Lab Assignment – I (HTML)
      • Lab Assignment – II (CSS)
      • Lab Assignment – III (JavaScript and XML)
      • Lab Assignment – IV (PHP)
      • Web Technology
        • php
          • Database connection using PHP and MySQL
          • Login form
          • Login form
  • 6th Semester
    • Compiler Design and Construction
    • NET Centric Computing
      • Class Codes
        • Authentication and Authorization in ASP.NET
        • C# Basics
      • Lab Codes
        • Practical 1
        • Practical 2
          • Number Operations Web App
          • User Registration Form
          • User Registration Console App
        • Practical 3
          • Authentication and Authorization (Claims, Roles and Policies)
          • Client side state management in ASP.NET
          • Entity Framework Core
          • Form Validation
            • React form validation
          • HTML Tag Helpers
          • MVC demonstration
          • Razor Syntax
          • Server Side State Management in ASP.NET
      • Self Projects
        • Do while programs
        • Role playing game battle challenge
        • Project overview
        • Authentication
          • wwwroot
            • lib
              • jquery-validation
                • The MIT License (MIT)
  • 7th Semester
    • Advanced Java Programming
      • Class Codes
        • Unit1-6&8
          • javafx-sdk-21.0.1
            • legal
              • javafx.graphics
                • Independent JPEG Group (IJG) JPEG v9e
                • Mesa 3-D Graphics Library v21.0.3
              • javafx.media
                • Microsoft DirectShow Samples v156905
                • GNU Glib v2.72.0
                • GStreamer v1.20.1
                • LibFFI v3.4.4
              • javafx.web
                • IBM International Components for Unicode (ICU4C) v73.1
                • xmlsoft.org: libxml2 v2.10.4
                • xmlsoft.org: libxslt v1.1.35
                • WebKit Open Source Project: WebKit v616.1
          • src
            • main
              • java
                • Unit 1: Programming in Java
                  • 2. Concepts and Topics
                • Unit 2: User Interface Components with Swing
                • Unit 3: Event Handling
                • Unit 4: Database Connectivity
                • Unit 5: Network Programming
                • Unit 6: GUI with JavaFX
        • Unit7
          • src
            • main
              • webapp
                • index
      • Lab Codes
        • Lab
          • src
            • main
              • java
                • Practical 1
                • Practical 2
                • Practical 3
                • Practical 4
                • Practical5
    • Data warehouse and Data mining
  • docs
    • Contributor Covenant Code of Conduct
Powered by GitBook
On this page
  • Programs:
  • Factorial
  • Fibonacci
  • G.C.D
  • Tower of Hanoi

Was this helpful?

  1. 3rd Semester
  2. Data Structures and Algorithms

Recursion

PreviousQueueNextLinked List

Last updated 8 months ago

Was this helpful?

Recursion means "defining a problem in terms of itself".

Recursion is a very important concept in computer science.

Programs:

Factorial

The factorial of a positive number n is given by:

factorial of n (n!) = 1 * 2 * 3 * 4 *...  * n
  • The factorial of a negative number doesn't exist.

  • The factorial of 0 is 1.

Fibonacci

The Fibonacci sequence is a sequence of numbers where the first two numbers are 0 and 1.

The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

In mathematical terms,

  • the sequence Fn of Fibonacci numbers is defined by the recurrence relation

fn = fn-1 + fn-2
  • with seed values

f0 = 0 and f1 = 1.

G.C.D

Greatest Common Divisor (G.C.D) is the largest number that divides both the given numbers without a remainder.

A simple and old approach is Euclidean algorithm by subtraction

It is is a process of repeat subtraction, carrying the result forward each time until the result is equal to the any one number being subtracted. If the answer is greater than 1, there is a GCD (besides 1). If the answer is 1, there is no common divisor (besides 1), and so both numbers are coprimes

pseudo code for above approach:

int gcd(a, b){
 if (a == b)
    return a
 if (a > b)
    gcd(a – b, b)
 else
    gcd(a, b – a)
 }

At some point one number becomes factor of the other so instead of repeatedly subtracting till both become equal , we check if it is factor of the other .

Tower of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
- No disk may be placed on top of a smaller disk.
Factorial
Fibonacci
G.C.D
Tower of Hanoi
Tower of Hanoi Illustration