FACULTY OF INFORMATION TECHNOLOGY
Semester 1, 2025/2026
Toy
-String name
Inventory -double price
-int available
+boolean contain(String name) +boolean isName(String name)
MTInventory ConsInventory
-Toy first
+boolean contain(String name) -Inventory rest
+boolean contain(String name)
DS – NLU 2
//in class MTInventory
public boolean contains(String toyName) {
return false;
}
// in class ConsInventory
public boolean contains(String toyName) {
return [Link](toyName)
|| [Link](toyName);
}
//in class Toy
public boolean isName(String toyName) {
return [Link](toyName);
}
DS – NLU 3
4
A method of solving a problem where the solution depends on
solutions to smaller instances of the same problem.
Recursion is the process of defining something in terms of
itself.
An algorithm is recursive if it calls itself to do part of its work.
It includes 2 parts:
◦ The base case handling a simple input that can be solved without
resorting to a recursive call
◦ The recursive case containing one or more recursive calls to the
algorithm
DS – NLU 5
A recursive algorithm must
eventually terminate.
A recursive algorithm must have at
least one base case, or stopping
case.
A base case does not execute a
recursive call.
DS – NLU 6
How many students total are directly behind you in your
"column" of the classroom?
You have poor vision ➔ you can see only the people right
next to you. So, you can't just look back and count.
But you are allowed to
ask questions of the person
next to you.
How can we solve this problem?
( recursively!)
DS – NLU 7
Recursion is all about breaking a big problem into smaller
occurrences of that same problem.
◦ Each person can solve a small part of the problem.
◦ What is a small version of
the problem that would be
easy to answer?
◦ What information from a
neighbor might help me?
DS – NLU 8
Number of people behind me:
◦ If there is someone behind me, ask him/her how many people are
behind him/her.
◦ When they respond with a value N,
then I will answer N + 1.
◦ If there is nobody behind me,
then I will answer 1.
DS – NLU 9
hello
hello
...
[Link]
DS – NLU 10
11
Linear recursion: makes at most one recursive call each time it
is invoked.
Binary recursion: algorithm makes two recursive calls.
Multiple recursion: method may make (potentially more than
two) recursive calls.
DS – NLU 12
Algorithm:
public int linearSum(int[] array, int n) {
if (n == 1)
return array[0];
else
return linearSum(array, n-1) + array[n-1];
}
DS – NLU 13
Algorithm:
public int binarySum(int[] array, int i, int n) {
if (n == 1)
return array[i];
else
return binarySum(array, i, [n/2]) +
binarySum(array, i+[n/2], [n/2]);
}
DS – NLU 14
Three resursions
public int tribonacci(int n) {
if (n == 0) return 0; // base case
if (n == 1 || n == 2) return 1; // base cases
// Three recursive calls
return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
}
DS – NLU 15
Factorial: the factorial of a positive integer n, denoted by n!, is
the product of all positive integers less than or equal to n:
Base case
Recursive case
DS – NLU 16
The function can also be written as a recurrence relation:
DS – NLU 17
Implemented Java code:
DS – NLU 18
A recursion trace for the call factorial(5)
Method calling
Value returning
DS – NLU 19
This factorial function can also be described without using
recursion :
Pseudocode (iterative)
input: integer n such that n >= 0
output: [n × (n-1) × (n-2) × … × 1]
(1). create new variable called running_total with a value of 1
(2). begin loop
1. if n is 0, exit loop
2. set running_total to (running_total × n)
3. decrement n
4. repeat loop Recursive version
(3). return running_total Or
end factorial Iterative version?
DS – NLU 20
Avoidance of unnecessary calling of functions.
A substitute for iteration where the iterative solution is very
complex.
Extremely useful when applying the same solution.
Leads to elegant, simplistic, short Java code (when used well).
DS – NLU 21
DS – NLU 22
Common reasons for using recursion:
◦ The problem is naturally recursive (e.g. Fibonacci)
◦ The data is naturally recursive (e.g. filesystem)
◦ Take more advantage of immutability:
all variables are final, all data is immutable, and the recursive methods are
all pure functions ➔ they do not mutate anything.
Recursion is that it may take more space than an iterative
solution (downside)
DS – NLU 23
The problem structure lends itself naturally to a recursive
definition.
◦ Ex.: factorial, Fibonacci, …
The data you are operating on is inherently recursive in
structure.
◦ Ex.: A filesystem consists of named files. Some files are folders, which
can contain other files
DS – NLU 24
The base case is missing entirely, or
◦ the problem needs more than one base case but not all the base cases
are covered.
DS – NLU 25
The recursive step doesn’t reduce to a smaller subproblem, so
the recursion doesn’t converge.
DS – NLU 26
For a given array of integers, implement a method, called
reversePrint to display the array reversely.
Ex. arr= { 1, 2, 3, 4, 5 } ➔ { 5, 4, 3, 2, 1 }
How to implement reversePrint method?
◦ It’s easy if using iterative approach
◦ How about recursive approach?
DS – NLU 27
For a given array of integers, implement a method, called
reversePrint to display the array reversely.
Hint: using a helper method
DS – NLU 28
Advantages:
◦ Simplifies code for complex problems.
◦ Natural fit for problems involving subproblems.
Disadvantages:
◦ Can be less efficient (memory).
◦ Risk of stack over flow with deep recursion.
DS – NLU 29
30
n
Calculation arithmetic series ( sigma ) recursive Sum
x
x =1
Iterative approach???
DS – NLU 31
How to calculate power:
x = x * x *...* x
y
y times
Iterative approach???
DS – NLU 32
How to calculate product?
x* y
DS – NLU 33
If the method stars1 is called with the value 3, is it equivalent
to the method stars2?
Explain!
DS – NLU 34
Apply the recursive approach to reversely print elements in a
given array:
Input={1,2,3} ➔ Output: 3 2 1
DS – NLU 35
Given a decimal number as input, how to convert the given
decimal number into equivalent binary number.
DS – NLU 36
Given a decimal number as input, how to convert the given
decimal number into equivalent binary number.
findBinary(decimal) {
if (decimal == 0)
binary = 0
else
binary = decimal % 2 + 10 * (finBinary(decimal/2))
}
DS – NLU 37
Other approaches:
◦ Using [Link](number): returns a string representation
of the integer argument as an unsigned integer in binary
◦ Using iterative method?
DS – NLU 38
How to draw the markings of a typical English ruler?
The length of the tick designating a whole inch as the major tick
length.
Between the marks for whole inches, the ruler contains a series of
minor ticks, placed at intervals of 1/2 inch, 1/4 inch, and so on.
As the size of the interval decreases by half, the tick length
decreases by one.
DS – NLU 39
DS – NLU 40
A mathematical puzzle where we have three rods and n disks.
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.
DS – NLU 41
The minimum number of moves required to solve is 2n - 1,
where n is the number of discs.
DS – NLU 42
Label the pegs A, B, C
Let n be the total number of discs
Number the discs from 1 (smallest, topmost) to n (largest,
bottommost)
To move n discs from rod A to rod C:
◦ Step 1. move n−1 discs from A to B. This leaves disc n alone on peg A
◦ Step 2. move disc n from A to C
◦ Step 3. move n−1 discs from B to C
DS – NLU 43
Image illustration for 3 discs :
1
2
3
DS – NLU 44
For given 3 discs with order: disk 1 < disk 2 < disk 3. How to
move all disks to C from A?
◦ Step 1: Move discs 2 and smaller from peg A (source) to peg B (spare),
using peg C (dest) as a spare
DS – NLU 45
For given 3 discs with order: disk 1 < disk 2 < disk 3. How to
move all discs to C from A?
◦ Step 2: With all the smaller discs on the spare peg, we can move disk 3
from peg A (source) to peg C (dest).
DS – NLU 46
For given 3 discs with order: disk 1 < disk 2 < disk 3. How to
move all disks to C from A?
◦ Step 3: We want discs 1 and smaller moved from peg C (spare) to peg B
(dest)
DS – NLU 47
Supposesource=A, dest=C, and spare=B, disk represents the
number of disks.
DS – NLU 48
Fibonacci: next number is the sum of previous two numbers
Ex. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Two approaches:
◦ Fibonacci Series without using recursion
◦ Fibonacci Series using recursion
DS – NLU 49
Pascal’s triangle: a triangular array of the binomial coefficients
DS – NLU 50
0
=1
0
n n − 1 n − 1
= +
k k − 1 k
DS – NLU 51
DS – NLU 52
DS – NLU 53
S(n)=1-2+3-4+…+ ((-1) (n+1) ).n , n>0
S(n)=1+1.2+1.2.3+…+1.2.3…n, n>0
S(n)=12+22+32+....+n2 , n>0
S(n)=1+1/2+1/(2.4)+1/(2.4.6)+…+1/(2.4.6.2n), n>=0
DS – NLU 54
FACULTY OF INFORMATION TECHNOLOGY