Recursion
- A function that calls itself
- Box analogy: to find a key in nested boxes, keep opening boxes — if it contains a box, open it; if it’s the key, stop
- Use recursion when it makes the solution clearer, not for performance
- An iterative solution usually exists and is sometimes faster
- “Loop may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer.” — Leigh Cladwell
Base Case and Recursive Case
- Easy to write a recursive function that ends up in an infinite loop
- Recursive calls should know when to stop — that’s the base case
- Every recursive function has two parts:
- Base case — when to stop
- Recursive case — when to keep calling yourself
- If the base case is never met, you get an infinite loop
void Print(int n){
Console.WriteLine(n)
if(n == 0){
return;
}
else{
return Print(n-1);
}
}