Transcript recursion when to use

When to use recursion
Computer Science 4
Mr. Gerb
Reference:
Objective: Understand when recursion is useful
and how to remove it.
Three rules of thumb: Use
recursion only when:
• The depth of recursive calls is relatively
“shallow” compared to the size of the
problem.
• The recursive version does about the same
amount of work as the nonrecursive version.
• The recursive version is shorter and simpler
than the nonrecursive solution.
Shallow recursive calls: First
Example
• Supposed you were to use recursion to
search a very large linked list with N
elements.
• O(N) stack frames might exist at one time
– Bad if N is large
– Most compilers have a limited amount of space
set aside for the stack
– Likely to cause a stack overflow
Shallow Recursive Calls: Second
Example
• Suppose you were to use recursion to binary
search an array of N elements
• O(LogN) stack frames will exist at one time
– OK even if N is large
– E.g. for 16 billion elements, only need 34 stack
frames!
– I.e. depth of recursion not a problem for binary
search
Recursive Version Works Same
as Non-Recursive Version
• Example: Nth fibonacci number:
public static int fib(int n){
if (n<=2)
return 1;
else
return fib(n-1)+fib(n-2);
}
• How many recursive calls does fib make?
Fibonacci Example Cont’d
• fib(1) and fib(2) both take none
• fib(3) takes two:
fib(1)
fib(2)
• fib(4) takes 4
fib(3)
fib(1)
fib(2)
fib(2)
fib(1)
fib(1)
fib(2)
fib(2)
• fib(5) takes 8
fib(4)
fib(2)
fib(3)
fib(3)
Fibonacci Example Cont’d
• fib(6) takes 14
fib(5)
fib(2)
fib(2)
fib(2)
fib(4)
fib(2)
fib(4)
fib(2)
fib(3)
fib(3)
fib(3)
fib(1)
fib(1)
fib(1)
fib(4)
fib(2)
fib(4)
fib(2)
fib(1)
fib(1)
fib(3)
fib(3)
fib(3)
fib(5)
fib(2)
fib(2)
• fib(7) takes 24
fib(6)
fib(1)
fib(1)
fib(1)
fib(4)
fib(2)
fib(5)
fib(2)
fib(2)
fib(2)
fib(3)
fib(3)
Fibonacci Example Cont’d
• fib(8) takes 40
fib(6)
fib(1)
fib(1)
fib(1)
fib(6)
fib(1)
fib(1)
fib(1)
fib(4)
fib(2)
fib(5)
fib(2)
fib(2)
fib(2)
fib(5)
fib(2)
fib(2)
fib(2)
fib(3)
fib(3)
fib(4)
fib(2)
fib(4)
fib(2)
fib(4)
fib(2)
fib(4)
fib(2)
fib(1)
fib(1)
fib(3)
fib(3)
fib(3)
fib(7)
fib(3)
fib(3)
fib(3)
fib(5)
fib(2)
fib(2)
Non-Recursive Fibonacci
public static void fib(int n){
int back1=1, back2=1,fib=1;
for (int ctr=3;ctr<=n;ctr++){
fib=back1+back2;
back2=back1;
back1=fib;
}
return fib;
}
Recursive vs. Non-Recursive
Fibonacci
• Non-recursive Fibonacci equires n-2 runs through
the loop
– fib(3) once through the loop
– fib(4) twice through the loop
– fib(8) six times through the loop
• Recursive Fibonacci requires an exponential
number of recursive calls
• Therefore computing Fibonacci numbers is not a
good candidate for recursion.
Recursive Function Shorter and
Simpler
• Many recursive algorithms would require
creating your own stack to implement nonrecursively
– Merge Sort
– Quick Sort
– Search
• Much simpler to express, understand,
implement and maintain using recursion
Two ways to remove recursion
• Use a stack
– Keep your own stack frames
– Rarely an improvement on the recursive solution
• Tail recursion
– When a function contains only one recursive call and it
is the last statement to be executed, that is called tail
recursion
– Tail recursion can be replaced by iteration to remove
recursion.
Example: Search an array for an item
public boolean fnd(int[] a, int n, int st){
if (st>a.length)
return false;
else if (a[st]==n)
return true;
else
return fnd(a,n,st+1);
}
int found = false;
while (!found &&
st<=a.length){
if (a[st]==n)
found = true;
st++
}
}
Summary
• Use recursion only when
– Recursion is not deep
– Doesn’t slow the algorithm down
– Easier to understand or implement
• Can remove recursion with a stack or tail
recursion
• Tail recursion
– One recursive call, last statement executed
– Recursion can be replaced with iteration