Data Loading...
Recursion - Computer Science Department, University of Waikato Flipbook PDF
COMP134B Programming 2 for engineers Recursion -9 How is the state of the previous call of the function remembered? Some
103 Views
34 Downloads
FLIP PDF 103.21KB
Recursion
Recursion
Recursion is concerned with describing a solution to a problem in terms of the solution itself:
In this lecture we will: Define the term recursion Demonstrate how the concept can be used in C++
We have been concerned with breaking large problems down into sub-problems
Study an introductory example of calculating factorial using recursion
So far, those sub-problems have been distinct from the larger problem
Consider further examples that reverse character input, sum an array of integers and searches an array of integers for a given value.
And the sub-solutions have been distinct from the overall solution But what if one of the sub-problems is exactly the same as the overall problem? This is called recursion, and is a powerful mechanism in programming languages.
COMP134B Programming 2 for engineers
Recursion - 1
Using recursion: factorial example
Recursion - 2
COMP134B Programming 2 for engineers
Using recursion: factorial example
“n factorial”—written n!— is equivalent to: Another way of looking at the factorial calculation is:
n * (n-1) * (n-2) * …… * 2 * 1 Zero factorial (0!) is defined to be equal to 1
n! = n * (n-1) * (n-2) * …… * 2 * 1 One way to implement this in C++, using only the mechanisms discussed so far, is:
Q. what is this equivalent to? A. (n-1)!
int factorial(int n) { int result = 1;
So :
for (int i = n; i > 0; i--) result = result * i;
n! =
1
or n * (n-1)!
(if n==0) (if n > 0)
return result; }
COMP134B Programming 2 for engineers
Recursion - 3
COMP134B Programming 2 for engineers
Recursion - 4
Using recursion: factorial example Writing this as pseudo code:
Using recursion: factorial example A recursive function calls itself to produce a solution
factorial(n) if n==0 result is 1 else result is n * factorial(n-1)
What would happen if we left out some of the code? int factorial(int n) { return (n * factorial(n-1)); }
Here a sub-solution has been defined in terms of the higher level solution
The function would continually call itself until the computer ran out of memory
Expressed as a recursive C++ function int factorial(int n) { if (n==0) return 1; else return (n * factorial(n-1)); }
So, in addition to a call to itself, a recursive function must contain a stopping condition that brings a halt to the recursive process
Recursion - 5
COMP134B Programming 2 for engineers
Recursion - 6
COMP134B Programming 2 for engineers
Factorial walkthrough
Factorial walkthrough
We can trace what happens:
We can trace what happens
int factorial(int n) { if (n==0) return 1; else return (n * factorial(n-1)); }
int factorial(int n) return point (next { action is the if (n==0) multiplication) return 1; else return (n * factorial(n-1)); } 24
factorial(4)
x = factorial(4)
return (4 *
factorial(4)
x = factorial(4)
)
factorial(3)
return (3 *
factorial(3)
)
return (3 * 2 )
factorial(2)
return (2 *
factorial(2)
)
return (2 * 1 )
factorial(1)
return (1 *
factorial(1)
)
return (1 * 1 )
factorial(0)
factorial(0)
return (1)
COMP134B Programming 2 for engineers
return (4 * 6 )
return (1)
Recursion - 7
COMP134B Programming 2 for engineers
Recursion - 8
Memory usage
Stacking function data
How is the state of the previous call of the function remembered?
empty stack
Some part of memory is put aside—the stack Information about each function call is placed on top of that for the previous call in the stack Only the top item is accessible When a call of the function is complete it is removed from the stack to reveal the information for the previous call
COMP134B Programming 2 for engineers
Recursion - 9
Stacking function data
Recursion - 10
Stacking function data
empty stack
empty stack
factorial(3) function call
factorial(3), n==3
COMP134B Programming 2 for engineers
factorial(3) function call
this is a stack frame
factorial(3), n==3
it is a segment of memory that holds • function parameters • the function's local variables • the return address (i.e. where the next instruction is to be found when the function is finished)
COMP134B Programming 2 for engineers
Recursion - 11
factorial(2) function call
factorial(2), n==2 factorial(3), n==3
COMP134B Programming 2 for engineers
Recursion - 12
Stacking function data
Stacking function data
empty stack
empty stack
factorial(3) function call
factorial(3) function call
factorial(3), n==3
factorial(3), n==3
factorial(2) function call
factorial(2) function call
factorial(2), n==2
factorial(2), n==2
factorial(3), n==3
factorial(3), n==3
factorial(1) function call
factorial(1) function call
factorial(1), n==1
factorial(1), n==1
factorial(2), n==2
factorial(2), n==2
factorial(3), n==3
factorial(3), n==3 factorial(0) function call
factorial(0), n==0 factorial(1), n==1 factorial(2), n==2 Recursion - 13
COMP134B Programming 2 for engineers
Stacking function data
factorial(3), n==3
Stacking function data
empty stack
empty stack
factorial(3) function call
factorial(3) function call
factorial(3), n==3
factorial(3), n==3
factorial(2) function call
factorial(2) function call
factorial(2), n==2
factorial(2), n==2
factorial(3), n==3
factorial(3), n==3
factorial(1) function call
factorial(1) function call
factorial(1), n==1
factorial(1), n==1
factorial(2), n==2
factorial(2), n==2
factorial(3), n==3
factorial(3), n==3
factorial(0) function call
factorial(3), n==3
factorial(0), n==0 return value 1
factorial(2), n==2 COMP134B Programming 2 for engineers
factorial(3), n==3
factorial(2), n==2 return value 1
factorial(0) function call
factorial(0), n==0 factorial(1), n==1
Recursion - 14
COMP134B Programming 2 for engineers
factorial(1), n==1
factorial(1), n==1
factorial(2), n==2
factorial(2), n==2
factorial(3), n==3
Recursion - 15
return value 1
COMP134B Programming 2 for engineers
factorial(3), n==3
factorial(1), n==1 factorial(2), n==2 factorial(3), n==3
Recursion - 16
Stacking function data
Stacking function data
empty stack
empty stack
factorial(3) function call
factorial(3) function call return value 6 to wherever factorial(3) was called from e.g. main function
factorial(3), n==3
factorial(3), n==3
factorial(2) function call
factorial(2) function call
factorial(2), n==2 factorial(3), n==3
factorial(2), n==2 return value 2
factorial(3), n==3
factorial(3), n==3
factorial(1) function call
return value 1
factorial(2), n==2
factorial(2), n==2
factorial(3), n==3
factorial(3), n==3
factorial(0) function call
factorial(3), n==3
factorial(0), n==0 return value 1
factorial(1), n==1
factorial(1), n==1
factorial(2), n==2
factorial(2), n==2 COMP134B Programming 2 for engineers
factorial(3), n==3
factorial(3), n==3
return value 1
factorial(2), n==2 Recursion - 17
Possible problem empty stack
factorial(2), n==2 return value 1
factorial(0) function call
factorial(0), n==0
factorial(3) function call
factorial(3), n==3
factorial(1), n==1
factorial(2), n==2
factorial(1), n==1
return value 2
factorial(1) function call
factorial(1), n==1
factorial(3), n==3
empty stack
COMP134B Programming 2 for engineers
factorial(3), n==3
factorial(1), n==1 factorial(2), n==2 factorial(3), n==3
Recursion - 18
Another example
What if we forgot to specify a valid stopping state?
Print out an input string backwards: #include void reverse(); int main() { reverse(); return 0; }
factorial(3), n==3 factorial(2) function call
we run out of stack space! program exits inelegantly in reality it would normally take many more recursive function calls
factorial(2), n==2 factorial(3), n==3 factorial(1) function call
void reverse() { char ch; cin.get(ch); if (ch != '\n') { reverse(); cout.put(ch); }
factorial(-2), n==-2 factorial(-1), n==-1 factorial(0), n==0
factorial(1), n==1
factorial(1), n==1
factorial(2), n==2
factorial(2), n==2
factorial(3), n==3
factorial(3), n==3
}
factorial(-2) function call
factorial(0) function call
factorial(-1), n==-1 factorial(0), n==0
factorial(0), n==0 factorial(1), n==1 factorial(2), n==2
factorial(-1) function call
COMP134B Programming 2 for engineers
factorial(3), n==3
factorial(1), n==1 factorial(2), n==2 factorial(3), n==3
Recursion - 19
COMP134B Programming 2 for engineers
Recursion - 20
Another example
Stacking function data empty stack
Assume input of
abc\n
Sum the contents of an int array include
reverse()
int sum(int[], int); void main() { int x[] = {1, 2, 3, 4, 5, 6};
empty stack get('a')
return to main function
cout