Unit 08: Recursion
This week's stuff:
Factorial: |
Summation: |
With our factorial, once we write out all of the steps we can hopefully begin to see a pattern:
This shows the Recursive Cases of the problem solving approach.
Instead, let's think of it in terms of a variable n...
n! = n * (n-1)!
Then, our terminating case here is when we finally stop repeating...
In this case, when we hit 1!:
1! = 1
Note that for a factorial, someone might ask "1!" or "0!", so I tend to make two terminating cases: if n == 1 or if n == 0 then we return 1.
We use this approach as well for something like the summations...
Figuring out the recursive case...
The terminating case...
We can translate these rules into code:
int Sum( int n )
{
if ( n == 1 ) { return 1; } // Terminating case
return n + Sum( n-1 ); // Recursive case
}
Summation | Draw line | Count up |
---|---|---|
Direct link: https://youtu.be/hoAx5JPjMh0 | Direct link: https://youtu.be/EAD-GVFVhWs | Direct link: https://youtu.be/5ULYCG1UZCY |
Example code: (repository)
Archived videos and class lectures:
Spring 2024