November 2020
Recursion
Chapter 2
Recursion
Data Structures & Algorithms
November 2020
2
Objectives
Recursion
In this chapter student will learn:
The concept of recursion
Using recursion to solve simple
problems
Data Structures & Algorithms
Using recursion to solve complex
problems
November 2020
3
Recursion
Recursion
Technique in which a method call itself.
Programming tactic that divide a
problem into sub-problems.
A method where the solution to a
problem depends on solutions to
Data Structures & Algorithms
smaller instances of the same problem
Easy way for complex problems
Each time the parameter become
smaller.
November 2020
4
Recursion
The power of recursion is in the possibility of
defining an infinite set of objects by a finite
statement. In the same manner, an infinite
number of computations can be described by
a finite recursive program.
Data Structures & Algorithms
A recursive function definition has one or
more base cases, meaning input(s) for which
the function produces a result trivially, & one
or more recursive cases, meaning input(s) for
which the program recurs / calls itself.
November 2020
5
Recursion
For example, the factorial function can be
defined recursively by the equations 0! =
1 and, for all n > 0, n! = n(n − 1)!.
Data Structures & Algorithms
November 2020
6
Recursion
Iteration
for statement
while statement
Recursion
Data Structures & Algorithms
November 2020
7
Drawbacks
Recursion
Non-efficiency for some problems
Overhead
Base case definition
Parameters
Data Structures & Algorithms
November 2020
8
Recursion
To solve a problem recursively do the
following:
Specify the problem
Specify the size of the problem for each
call
Data Structures & Algorithms
Specify the base case (s)
Specify the general case (s)
November 2020
9
Power
Recursion
public static int Tawan(int x, int y){
if (y < 1) return 1;
else return x*Tawan(x,y-1);
}
Data Structures & Algorithms
November 2020
10
Factorial
Recursion
n! = n*(n-1)*(n-2)*……3*2*1
Data Structures & Algorithms
November 2020
11
Recursion
public static int recursivefactorial(int n) {
if (n == 0) return 1;
else return n*recursivefactorial(n-1);
}
Data Structures & Algorithms
November 2020
12
Tracing
Recursion
Data Structures & Algorithms
November 2020
13
Decimal To Binary
Recursion
public void DecToBin(int n) {
if (n > 0 ) {
DecToBin (n/2);
[Link](n % 2);
Data Structures & Algorithms
}
}
November 2020
14
Euclidean Algorithm
Recursion
public class Euclidean {
public static void main(String[] args) {
[Link](gcd (60,25)); }
public static int gcd( int m, int n) {
Data Structures & Algorithms
if(m == n) return n;
else if (m < n) return gcd(m, n-m);
else return gcd(m-n,n);
}}
November 2020
15
Solving Complex Problem With
Recursion Recursion
Recursion is used for simplifying a
complex problems.
There are many examples which can be
simplified by recursion.
Here are some examples:
Data Structures & Algorithms
November 2020
16
Fibonacci Sequence
Recursion
1,1,2,3,5,8,13,21 …..
T(n) = T(n-1) + T(n-2)
Data Structures & Algorithms
November 2020
17
Recursion
public static long fib( int n) {
if (n<2) return n;
return fib(n-1) + fib(n-2);
}
Data Structures & Algorithms
}
November 2020
18
Binomial Coefficients
Recursion
(x+1)6 = x6 + 6x5 + 15x4 + 20x3 + 15x2 + 6x + 1
Pascal
Data Structures & Algorithms
v(r, c) = v(r-1, c-1) + v(r-1, c); for 0 < c <r
v(6, 2) = v(5, 1) + v(5, 2)
November 2020
19
Recursive solution for Binomial
Recursion Coefficients
public class binom {
public static void main(String[] args) {
for(int r=0; r<10;r++){
for(int c=0; c<=r; c++)
[Link](Binomial (r,c) + " ");
Data Structures & Algorithms
[Link]();} }
public static long Binomial ( int r, int c) {
if (c == 0 || c == r) return 1;
Return Binomial (r-1, c-1) + Binomial (r-1,c);
}}
November 2020
20
Tower of Hanoi
Recursion
function hanoi is:
input: integer n, such that n >= 1
1. if n is 1 then return 1
2. return [2 * [call hanoi(n-1)] + 1]
Data Structures & Algorithms
end hanoi
November 2020
21
Tower of Hanoi
Recursion
class towerApp {
static int ndisks =3;
public static void main (String[] args) {
Towers(ndisks, 'A', 'B', 'C');
Data Structures & Algorithms
}
November 2020
22
Recursion
public static void Towers(int topn, char from, char inter,
char to) {
if(topn == 1)
[Link]("Disk 1 from " + from + " to "
+ to);
Data Structures & Algorithms
else {
Towers(topn-1, from, to, inter);
[Link]("Disk " + topn + " from " +
from + " to " + to);
Towers(topn-1, inter, from, to);
} }}
November 2020
23
Recursion versus iteration
Recursion
Recursion can be replaced by iteration
with an explicit call stack, while
iteration can be replaced only with
recursion.
Which approach is preferable depends
Data Structures & Algorithms
on the problem under consideration and
the language used.
November 2020
24
Recursion
In imperative programming, iteration is
preferred, particularly for simple
recursion, as it avoids the overhead of
function calls.
By contrast, in functional languages
Data Structures & Algorithms
recursion is preferred, with tail
recursion optimization leading to little
overhead.
November 2020
25
Chapter Exercises
Recursion
Write a recursive method to calculate the
square sum of the first n numbers (12 + 22
+ 32 + …… n2)?
Write a recursive method to find base 2
logarithm of a given number?
Data Structures & Algorithms
Describe a recursive algorithm for finding
the maximum element in an array, A, of n
elements.
November 2020
26
Recursion
Draw the recursion trace for the
computation of power(2,5), using the
traditional algorithm
Write a short recursive Java method that
Data Structures & Algorithms
takes a character string s and outputs its
reverse.
End of Chapter 2
Question?