Recursive Methods and
Problem solving
BCSC 0015 Applied Data Structures and Algorithms
Index
1. Introduction to Recursion
2. Iterative Vs recursion
3. Head and tail recursion
4. Stack with recursion
5. Designing recursive algorithm
BCSC 0015 Applied Data Structures and Algorithms 2
Calling Methods
● Methods can call other methods
● Can a method call itself?
● Yes! This is called a recursive method (function)
● “A method within a method”
BCSC 0015 Applied Data Structures and Algorithms 3
Recursion
● A method/procedure where the solution to a problem depends on solutions to smaller
instances of the same problem
● So we break the task into smaller subtasks
● This approach can be applied to many types of problems and recursion is one of the
central ideas of computer science
● We have to define base cases in order to avoid infinite loops
● We can solve problems with recursion or with iteration.
BCSC 0015 Applied Data Structures and Algorithms 4
Add the first N numbers:
Usually we use a simple for/while loop but we can solve it with the help of recursive
method call.
public void sum(int N) public int recursionSum(int N)
{ {
Int smm =0; if(N==1) return 1; //base case
for(int i =1;i<=N;i++)
{ return N + recursionSum(N -1); // recursive call
sum=sum+i; }
}
System.out.println(sum);
}
ITERATION RECURSION
BCSC 0015 Applied Data Structures and Algorithms 5
Head Vs tail recursion
● If the recursive call occurs at the end of a method -> It is called a tail recursion
● The tail recursion is similar to a loop
● The method executes all the statements before jumping into the next recursive call
● If the recursive call occurs at the beginning of a method, it is called a head recursion.
● The method saves the state before jumping into the net recursive call.
BCSC 0015 Applied Data Structures and Algorithms 6
Head Vs tail recursion
public int tailRecursion(int N) public int headRecursion(int N)
{ {
If ( N == 1) return //base case If ( N == 1) return //base case
System.out.println(N); headRecursion(N-1);// recursive call
tailRecursion(N-1); System.out.println(N);
}
}
BCSC 0015 Applied Data Structures and Algorithms 7
Stack with recursion
● We have to track during recursion who called the given method and what arguments are
to be handed over
● AND WE HAVE TO TRACK THE PENDING CALLS !!!
● We just need a single stack data structure: the operating system does everything for us
by creating a run time stack.
● These important information are to be pushed to the stack called stack frames/ Activation
record
● Values are popped from the stack
BCSC 0015 Applied Data Structures and Algorithms 8
Stack with recursion
public int recursionSum(int N)
{
BASE CASE
if(N==1) return 1; //base case
return N + recursionSum(N -1); // 2 + recursionSum(1)
recursive call
}
3 + recursionSum(2)
4 + recursionSum(3)
BCSC 0015 Applied Data Structures and Algorithms 9
Stack with recursion
WHEN WE USED recursionSum(int N) method:
recursionSum(4)
recursionSum(3)
recursionSum(2)
recursionSum(1)
return 1
return 2+1
return 3+2+1
return 4+3+2+1
So these method calls like this and values are stored on the stack
Recursion is at least twice slower because first we unfold recursive calls(pushing
them on a stack) until we reach the base case and then we traverse the stack
and retrieve all recursive calls
BCSC 0015 Applied Data Structures and Algorithms 10
Recursion or Iteration?
● Moral: There is usually more than one way to solve a problem!
○ Iteration (loops to repeat code)
○ Recursion (nested function calls to repeat code)
● Tradeoffs between two options:
○ Sometimes recursive solution is easier
○ Recursive solution is often slower
BCSC 0015 Applied Data Structures and Algorithms 11
When to use Recursion / when to
avoid recursion
● When we easily breakdown a problem into smaller subproblem.
● When we are ok with extra overhead (both time and space) that comes
with it.
● When we need a quick working solution instead of efficient one.
BCSC 0015 Applied Data Structures and Algorithms 12
Facts about recursion
● Recursive methods call themselves
● Each call solves an identical problem
○ The code is the same!
○ Successive calls solve smaller/simpler instances
● Every recursive algorithm has at least one base case
○ A known/easy to solve case
○ Often, when we reach 1 or 0
BCSC 0015 Applied Data Structures and Algorithms 13
Designing Recursive Algorithm
General strategy: “Divide and Conquer”
Questions to ask yourself
How can we reduce the problem to smaller version of the same problem?
How does each call make the problem smaller?
What is the base case?
Will you always reach the base case?
BCSC 0015 Applied Data Structures and Algorithms 14
References
● Hyperskil Academy by jetbrains.
● Chris Kiekintveld CS 2401 (Fall 2010) Elementary Data Structures and Algorithms
BCSC 0015 Applied Data Structures and Algorithms 15
