Introduction to Recursion
What is Recursion?
• Recursion is when a function calls itself.
• Each time it runs, it works on a smaller part of the
problem.
• It solves a big problem by breaking it into smaller,
similar problems.
• Real-Life Example:
• Like searching inside folders within folders on
your computer.
Two Key Components of Recursion
Base Case
• The stopping condition.
• Prevents infinite recursion.
Recursive Case
• The function calls itself.
• Works on a smaller version of the problem.
• Without a base case → program causes StackOverflowError.
Base Case: The Stopping Condition
Why it's important ?
• The base case prevents infinite recursion.
• It defines when the recursion should stop.
• Without it, your program will crash with
StackOverflowError.
• Real-Life Example:
• Climbing down stairs – when you reach ground floor, you
stop.
Recursive Case: The Self-Call
How it works?
• The function calls itself.
• It works on a smaller version of the problem.
• Each call moves closer to the base case.
• Real-Life Example:
• Peeling an onion layer by layer until nothing
remains.
How Recursion Works Internally
Each function call is stored in memory
stack
When base case is reached
Calls start returning one by one
This is called call stack execution
Like stacking plates (LIFO – Last In First Out).
Recursion Syntax in Java
Basic Structure
Complete Java Example
Factorial Function
Output
Difference Between Both Methods
Without Recursion With Recursion
Uses loop Function calls itself
Simple and faster Easy to understand logically
No call stack usage Uses call stack memory
Better for large values May cause StackOverflow if very large
Task - 1
Code for Printing N Numbers 1 to N.
Step:1
Creating class and Recursive method
Code Explanation
• Scanner class
• import [Link];
• Imports the Scanner class.
• Used to take input from the user.
• Defining class name
• public class PrintNumbers
• Defines a class named PrintNumbers.
• Recursive Method
• static void print(int n) – It is a recursive method, takes one parameter ‘n’
and print numbers from ‘1’ to ‘n’
Step:2
Creating Object and calling Recursive
method
Code Explanation
• Creating Scanner Object
• Scanner sc = new Scanner([Link]);
• Scanner is used to take input from the user.
• [Link] means input comes from the keyboard.
• sc is the object name.
• Asking User for Input
• [Link]("Enter a number: ");
• Displays a message on the screen.
• print() does not move to the next line after printing.
• Reading the Number
• int n = [Link]();
• Reads an integer value entered by the user and stores it in variable ‘n’.
Full Code:
Output:
Task - 2
Code for Printing N Numbers N to 1.
Step:1
Creating class and Recursive method
Code Explanation
• Scanner class
• import [Link];
• Imports the Scanner class.
• Used to take input from the user.
• Defining class name
• public class ReverseNumbers
• Defines a class named ReverseNumbers.
• Recursive Method
• static void printNumbers(int n) – It is a recursive method that takes one
parameter n and prints numbers from N to 1.
Step:2
Creating Object and calling Recursive
method
Code Explanation
• Creating Scanner Object
• Scanner sc = new Scanner([Link]);
• Scanner is used to take input from the user.
• [Link] means input comes from the keyboard.
• sc is the object name.
• Asking User for Input
• [Link]("Enter a number: ");
• Displays a message on the screen.
• print() does not move to the next line after printing.
• Reading the Number
• int n = [Link]();
• Reads an integer value entered by the user and stores it in variable n.
Full Code:
Output:
Introduction to Factorial
What is Factorial?
• Factorial of a number n is the product of all positive integers from 1 to
n.
• It is denoted as n!
• Example: 5! = 5 × 4 × 3 × 2 × 1 = 120
Mathematical Formula
n! = n × (n-1) × (n-2) × ... × 1
Special Cases:
• 0! = 1
• 1! = 1
Factorial Without Recursion
• Uses a loop
• Multiply numbers from 1 to n
• Store result in a variable
• No function calls itself
• Iterative Method
Task:3
Code Implementation for
printing factorial numbers
Code Explanation
• Declaration
• FactorialIterative – Defines the class name.
• Main Method
• public static void main(String[] args) {
• public → accessible everywhere.
• static → no object needed.
• Variable Declaration
• int n = 5; - Stores the factorial of the number which we want to calculate.
• int fact = 1; - fact stores the factorial result.
• Initialized to 1 because factorial multiplication starts from 1.
Code Explanation
• Main Logic
• for (int i = 1; i <= n; i++) {
fact = fact * i;
}
• Loop starts from i = 1
• Runs until i <= n
• Printing output
• [Link] is used to print the result.
Complete Code
Output
Factorial With Recursion
• Recursive Method
• Function calls itself
• Uses formula: n! = n × (n-1)!
• Base Case in Recursion
• if (n == 0 || n == 1) {
return 1;
}
Recursive Formula Explained
• Self-Referencing Definition
• The formula n! = n × (n-1)! defines the factorial of a
number by referring to the factorial of a smaller
number. It breaks down a larger problem into a
simpler, identical sub-problem.
• Function Calling Itself
• This method is called recursive because, in
programming, a function implementing this logic
would call itself repeatedly to solve the smaller
instances of the problem.
Recursive Formula Explained
• Problem Decomposition
• For instance, to calculate 5!, the formula uses 5 × 4!.
To find 4!, it then requires 4 × 3!, continuing until a
known value is reached.
• Essential Base Case
• A crucial 'base case' (like 0! = 1 or 1! = 1) is needed.
This stops the recursion from running infinitely and
provides a fundamental, non-recursive value from
which all other calculations can build.
How Recursion Works
• Example n = 4
• factorial(4)
• → 4 × factorial(3)
• factorial(3)
• → 4 × factorial(3)
• → 4 × 3 × factorial(2)
• factorial(2)
• → 4 × 3 × 2 × factorial(1)
• factorial(1)
• → 4 × 3 × 2 × 1 = 24
Step: 1
Declaring class method and Recursive
steps.
Code Explanation
• Class Declaration
• FactorialRecursive – Defines the class name.
• Method Declaration
• static int factorial(int n)
• static → Method belongs to the class (no object needed).
• int → Returns an integer value.
• factorial → Method name.
• int n → Input number.
• Stopping Condition
• (n == 0 || n == 1)
• This condition stops the recursion.
• Without it → infinite recursion → StackOverflowError.
• Can be also known as Base Case.
Code Explanation
•Recursive Step
•return n * factorial(n - 1);
•Method Calls itself.
•Reduces the value of n.
•Process Continues until it reaches the
base case.
Step: 2
Declaring Main Method and Factorial
Method.
Code Explanation
• Main Method
• public static void main(String[] args)
• public → Accessible from anywhere.
• static → Can run without creating an object.
• void → Does not return any value.
• String[] args → Used to take command-line inputs (not used here).
• Factorial Method
• int result = factorial(5);
• Calls the factorial method, passes the value needed as an argument and
calculates the factorial value then returned value will be stored in variable
Result.
• Printing output
• [Link] is used to print the result.
Complete Code
Output
Introduction to Fibonacci Series
What is Fibonacci Series?
• A sequence of numbers
• Each number is the sum of the previous two numbers
• Series: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Mathematical Formula
For n ≥ 2:
F(n) = F(n-1) + F(n-2)
Fibonacci Without Recursion
•Uses a loop
•Start with first two numbers (0 and 1)
•Continue adding previous two numbers
•No function calls itself
•Iterative Method
Task:4
Code Implementation for printing
Fibonacci Series
Step: 1
Creating class, main method and variable
declaration.
Code Explanation
• Class Declaration
• class FibonacciIterative { - Defines a class named FibonacciIterative.
• Main Method
• public static void main(String[] args)
• Starting point of the program.
• Variable Declaration
• int n = 10; - n represents how many Fibonacci numbers to print.
• int a = 0, b = 1;
• a = first number of Fibonacci series.
• b = second number of Fibonacci series.
Code Explanation
• Printing output
• [Link] is used to print the
result.
Step: 2
Creating a loop and calculating
next Fibonacci number
Code Explanation
• Loop Structure
• for (int i = 2; i < n; i++)
• i = 2 → Because first two numbers (0 and 1) are already printed.
• i < n → Loop runs until we print n numbers.
• i++ → Increase i after each iteration.
• Calculate Next Fibonacci Number
• int c = a + b;
• Next number = sum of previous two numbers.
• c stores the next Fibonacci number.
• Print the Number
• [Link](c + " ");
• Prints the newly generated number.
• Update Values
• a = b; , b = c;
• Move values forward.
• The old b becomes new a.
• The new c becomes new b.
Complete Code
output
Fibonacci With Recursion
• Function calls itself
• Uses formula: F(n) = F(n-1) + F(n-2)
• Recursive Method
• Base Case in Recursion
• If n == 0 → return 0
• If n == 1 → return 1
• This stops recursion
Step : 1
Creating class and method
declaration
Code Explanation
• Class Declaration
• class FibonacciRecursive {
• Defines a class named FibonacciRecursive.
• Method Declaration
• static int fibonacci(int n)
• static → No object required.
• int → Returns an integer.
• n → Position of Fibonacci number.
• Base Case 1
• if (n == 0)
return 0;
• First Fibonacci number is 0.
• Stops recursion when n = 0.
Code Explanation
• Base Case 2
• if (n == 1)
return 1;
• Second Fibonacci number is 1.
• Stops recursion when n = 1.
• Important to avoid infinite recursion.
• Recursive Step
• return fibonacci(n - 1) + fibonacci(n - 2);
• F(n) = F(n-1) + F(n-2)
• Function Calls itself twice.
• Reduces the value of n.
• Keeps calling until it reaches 0 or 1.
Step: 2
Creating Main Method, Fibonacci
method and For Loop
Code Explanation
• Main Method
• public static void main(String[] args)
• This is the starting point of the Java program.
• For Loop
• for (int i = 0; i < 10; i++)
• i = 0 → Loop starts from 0.
• i < 10 → Loop runs until i becomes 9.
• i++ → Increases i by 1 each time.
• loop runs 10 times (from 0 to 9).
• Calling the fibonacci Method
• [Link](fibonacci(i) + " ");
• Calls fibonacci(i) for each value of i.
• Prints the returned Fibonacci number.
• " " adds a space after each number.
Complete Code
Output