Transcript Slide 1

1
CS212: DATASTRUCTURES
Lecture 4: Recursion
Lecture Contents
2





The Concept of Recursion
Why recursion?
Factorial – A case study
Content of a Recursive Method
Recursion vs. iteration
The Concept of Recursion
3




repetition can be achieved by writing loops, such as for loops and while
loops.
Another way to achieve repetition is through recursion, which occurs when a
function calls itself.
A recursive function is a function that calls itself , either directly or indirectly
( through another function).
For example :
void myFunction( int counter)
{
if(counter == 0)
return;
else
{
myFunction(--counter);
return;
}
}
Why recursion?
4



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
Allows very simple programs for very complex
problems
Factorial – A case study
5

Factorial definition: the factorial of a number is
product of the integral values from 1 to the number.
factorial 3
=
3*2*1
=
6
Factorial – A case study
6

Iteration algorithm definition (non-recursive)
1
if n = 0
n*(n-1)*(n-2)*…*3*2*1
if n > 0
Factorial(n) =
factorial 4
=
product [4..1]
=
product [4,3,2,1]
=
4*3*2*1
=
24
Factorial – A case study
7

Recursion algorithm definition
1
if n = 0
n * ( Factorial(n-1) )
if n > 0
Factorial(n) =
=
factorial 3
=
3 * factorial 2
=
3 * (2 * factorial 1)
=
3 * (2 * (1 * factorial 0))
=
3 * (2 * (1 * 1))
=
3 * (2 * 1)
=
3 * 2
76
Content of a Recursive Method
8
Base case(s).
 One or more stopping conditions that can be directly evaluated for certain

arguments
 there should be at least one base case.

Recursive calls.
 One or more recursive steps, in which a current value of the method can be
computed by repeated calling of the method with arguments (general
case).
 The recursive procedure call must use a different argument that the original
one: otherwise the procedure would always get into an infinite loop…
Content of a Recursive Method
9
Use an if-else statement to
distinguish between a Base case
and a recursive step
void myFunction( int counter)
{
if( counter == 0)
…........
else
{
………
myFunction(--counter);
}
}
Iterative factorial algorithm
Recursive factorial Algorithm
public static int recursiveFactoria(int n) {
public static int recursiveFactoria(int n) {
10
i=1
factN = 1
for(int i=1; i<= n; i++)
factN = factN * i
i=i+1
return factN
if (n == 0)
return 1; // base case
else
return n * recursiveFactorial(n-1): //
recursive case
}
}
recursive implementation of the factorial function is somewhat simpler than the
iterative version in this case there is no compelling reason for preferring recursion
over iteration.
For some problems, however, a recursive implementation can be significantly
simpler and easier to understand than an iterative implementation.
Tracing Recursive Method
11
• Each recursive call is made with a new
arguments Previous calls are suspended
• Each entry of the trace corresponds to a
recursive call.
•
Each new recursive function call is
indicated by an arrow to the newly
called function.
• When the function returns, an arrow
showing this return is drawn and the
return value may be indicated with this
arrow.
Recursion vs. iteration
12



Iteration can be used in place of recursion
 An iterative algorithm uses a looping construct
 A recursive algorithm uses a branching structure(ifstatement)
Recursive solutions are often less efficient, in terms
of both time and space, than iterative solutions
Recursion can simplify the solution of a problem,
often resulting in shorter, more easily understood
source code
Recursion
13
1 Linear Recursion
2 Binary Recursion
3 Multiple Recursion
1 Linear Recursion
14

The simplest form of recursion is linear recursion,
where a method is defined so that it makes at most
one recursive call each time it is invoked.
Summing the Elements of an Array Recursively
15
Algorithm LinearSum(A , n )
input
A integer array A and an integer
n>=1, such that A has at least n
elements
output
The sum of the first n integers in A
if (n = 1) then
return A[0]
else
return LinearSum(A, n - 1) + A[n - 1]
A=
4
n=5
3
6
2
5
Summation (Sigma) Notation
16
Algorithm sum ( n <integer>)
Input
n is an integer number
o𝒖𝒕𝒑𝒖𝒕
𝑛
𝑖=1 𝑖 is returned
if (n == 1)
return 1;
else
return n + sum(n-1);
End IF
Summation (Sigma) Notation
con..
17
 For n =3
return 6
Sum (3)
return 3+Sum(2)
return 3+3
return 3
Sum(2)
return 2+ sum(1)
return 2+1
return 1
Sum(1)
return 1
Printing “Hello World” n Times Using Recursion
18
Algorithm printHelloWorld ( n <integer>)
Input
n is an integer number
Output
“Hello World” printed n times
If ( n >0 )
{
Print “Hello World”
printHelloWorld( n – 1 );
}
Printing “Hello World” n Times Using Recursion
19
hello world
return
printHelloWorld(3)
Print hello world
printHelloWorld(2)
return
hello world
printHelloWorld(2)
Print hello world
printHelloWorld(1)
hello world
printHelloWorld(1)
Print hello world
printHelloWorld(0)
return
return
printHelloWorld(0)
2 Binary Recursion
20

When an algorithm makes two recursive calls, we
say that it uses binary recursion. These calls can, for
example, be used to solve two similar halves of
some problem,
21
Computing Fibonacci Numbers via
Binary Recursion






Let us consider the problem of computing the kth
Fibonacci number.
{0, 1, 1, 2, 3, 5, 8, 13, 21, 34,….}
Fibonacci numbers are recursively defined as follows:
F0 = 1
F1 = 1
Fi = Fi−1 + Fi−2.
Computing Fibonacci Numbers con..
22
Algorithm BinaryFib(k):
Input:
Nonnegative integer k
Output:
The kth Fibonacci number f
if (k< I) then
return k
else
return BinaryFib(k - 1) + BinaryFib(k -2)
Calculate BinaryFib(3)
23
Exercise
24
what is the output of fun(16)?
Algorithm fun(int X)
if ( x <=4 )
return 1
else
return fun(x/4) + fun (x/2)
Result = 3
3 Multiple Recursion
25

Generalizing from binary recursion, we use multiple
recursion when a method may make multiple
recursive calls, with that number potentially being
more than two.
26
End Of Chapter