Discrete Structures
(Discrete Mathematics)
Recursion
Asim Raza
Email: [Link]@[Link]
University of Central Punjab, Lahore
Recursion – Definition
Sometimes, the best way to solve a problem is by solving a smaller
version of the exact same problem first
Recursion is a technique that solves a problem by solving a smaller
problem of the same type
Recursion is: Recursive Methods
A problem-solving approach, that can ...Must Eventually Terminate
Generate simple solutions to ...
Certain kinds of problems that ...
Would be difficult to solve in other ways
Recursion splits a problem:
Into one or more simpler versions of itself
Key Elements of Recursion
1. What is a smaller identical problem(s)?
Decomposition
2. How are the answers to smaller problems combined
to form the answer to the larger problem?
Composition
3. Which is the smallest problem that can be solved
easily (without further decomposition)?
Base/stopping case
Recursive Versus Iterative
Methods
All recursive algorithms/methods
can be rewritten without recursion.
Iterative methods use loops instead of recursion
Iterative methods generally run faster and use less
memory--less overhead in keeping track of method
calls
So When Should You Use
Recursion?
Solutions/algorithms for some problems are
inherently recursive
iterativeimplementation could be more
complicated
When efficiency is less important
it might make the code easier to understand
Bottom line is about:
Algorithm design
Tradeoff between readability and efficiency
Factorial – First Example
N! = (N-1)! * N [for N > 1] public static int factorial(int n)
{
1! = 1 int fact;
3! if (n > 1) // recursive case
(decomposition)
= 2! * 3 fact = factorial(n – 1) * n; //
= (1! * 2) * 3 composition
else // base case
=1*2*3 fact = 1;
Recursive design:
return fact;
Decomposition: (N-1)! }
Composition: * N
Base case: 1!
public static int factorial(int 3)
{
int fact;
if (n > 1)
fact = factorial(2) * 3;
else
fact = 1;
return fact;
}
public static int factorial(int 2)
{
int fact;
if (n > 1)
fact = factorial(1) * 2;
else
fact = 1;
return fact;
}
public static int factorial(int 1)
{
int fact;
if (n > 1)
fact = factorial(n - 1) * n;
else
fact = 1;
return fact;
}
public static int factorial(int n)
Execution {
int fact;
if (n > 1) // recursive case (decomposition)
Trace fact = factorial(n – 1) * n; (composition)
else // base case
(decompositio
fact = 1;
return fact;
}
n)
factorial(4)
factorial(3) 4
factorial(2) 3
factorial(1) 2
public static int factorial(int n)
Execution {
int fact;
if (n > 1) // recursive case (decomposition)
Trace fact = factorial(n – 1) * n; (composition)
else // base case
(composition)
fact = 1;
return fact;
}
*
factorial(3) 4
*
factorial(2) 3
*
factorial(1)->1 2
Factorial – First Example
N! = (N-1)! * N [for N > 1] public static int factorial(int n)
{
1! = 1 int fact;
3! if (n > 1) // recursive case
(decomposition)
= 2! * 3 fact = factorial(n – 1) * n; //
= (1! * 2) * 3 composition
else // base case
=1*2*3 fact = 1;
Recursive design:
return fact;
Decomposition: (N-1)! }
Composition: * N
Base case: 1!
Fibonacci Numbers – Second Example
The Nth Fibonacci number is the sum of the previous two
Fibonacci numbers
0, 1, 1, 2, 3, 5, 8, 13, …
Recursive Design:
Decomposition & Composition
Fibonacci (n) = Fibonacci (n - 1) + Fibonacci (n - 2)
Base case:
Fibonacci (1) = 0
Fibonacci (2) = 1
Fibonacci Numbers – Second Example
public static int fibonacci(int n)
{
int fib;
if (n > 2)
fib = fibonacci(n-1) + fibonacci(n-2);
else if (n == 2)
fib = 1;
else
fib = 0;
return fib;
}
Fibonacci Numbers – Second Example
Execution Trace (decomposition)
fibonacci(4)
fibonacci(3) fibonacci(2)
fibonacci(2) fibonacci(1)
Fibonacci Numbers – Second Example
Execution Trace (composition)
fibonacci(4)
+
fibonacci(3) fibonacci(2)
+
fibonacci(2)->1 fibonacci(1)->0
Remember:
Key to Successful Recursion
if-else
statement (or some other branching
statement)
Some branches: recursive call
"smaller" arguments or solve "smaller" versions of the same task
(decomposition)
Combine the results (composition) [if necessary]
Other branches: no recursive calls
stopping cases or base cases
Warning: Infinite Recursion May
Cause a Stack Overflow Error
Infinite Recursion
Problem not getting smaller (no/bad decomposition)
Base case exists, but not reachable (bad base case
and/or decomposition)
No base case
Stack: keeps track of recursive calls by JVM (OS)
Method begins: add data onto the stack
Method ends: remove data from the stack
Recursion never stops; stack eventually runs out of space
Stack overflow error
Number of Zeros in a digit: Third Example
Example: 2030 has 2 zeros
recursive
If n has two or more digits
the number of zeros is the number of zeros
in n with the last digit removed
plus an additional 1 if the last digit is zero
Examples:
number of zeros in 20030 is number of zeros
in 2003 plus 1
number of zeros in 20031 is number of zeros
in 2003 plus 0
numberOfZeros Recursive
Design
numberOfZeros in the number N
K = number of digits in N
Decomposition:
numberOfZeros in the first K - 1 digits
Last digit
Composition:
Add:
numberOfZeros in the first K - 1digits
1 if the last digit is zero
Base case:
N has one digit (K = 1)
numberOfZeros method
public static int numberOfZeros(int n)
{
int zeroCount; Which is (are)
if (n==0) the base
zeroCount = 1; case(s)? Why?
else if (n < 10) // and not 0
zeroCount = 0; // 0 for no zeros Decompostion,
else if (n%10 == 0) Why?
zeroCount = numberOfZeros(n/10) + 1;
else // n%10 != 0 Composition,
zeroCount = numberOfZeros(n/10); why?
return zeroCount;
}
public static int numberOfZeros(int n)
{
Execution int zeroCount;
if (n==0)
Trace zeroCount = 1;
else if (n < 10) // and not 0
(decompositio
Each method
zeroCount = 0; // 0 for no zeros
else if (n%10 == 0)
n)
invocation will zeroCount = numberOfZeros(n/10) + 1;
execute one of else // n%10 != 0
zeroCount = numberOfZeros(n/10);
the if-else return zeroCount;
cases shown at }
right.
numberOfZeros(2005)
numberOfZeros(200) 5
numberOfZeros(20) 0
numberOfZeros(2) 0
public static int numberOfZeros(int n)
{
Execution int zeroCount;
if (n==0)
Trace zeroCount = 1;
else if (n < 10) // and not 0
(composition)
Recursive calls
zeroCount = 0; // 0 for no zeros
else if (n%10 == 0)
return zeroCount = numberOfZeros(n/10) + 1;
else // n%10 != 0
zeroCount = numberOfZeros(n/10);
return zeroCount;
}
numberOfZeros(2005)->2
+
numberOfZeros(200)->2 5->0
+
numberOfZeros(20)->1 0->1
+
numberOfZeros(2)->0 0->1