KwickClips Java · 45 sec · free
What is the base case of GCD?
Short answer. When b becomes 0, the answer is a.
Why is recursive Fibonacci slow?
Each call makes two more calls.
Base and recursive
| Program | Base | Recursive |
|---|---|---|
| fact(n) | n<=1: 1 | n*fact(n-1) |
| fib(n) | n<=1: n | f(n-1)+f(n-2) |
| gcd(a,b) | b==0: a | gcd(b,a%b) |
| pow(b,e) | e==0: 1 | b*pow(b,e-1) |
Remember
| Find the base case first |
| Then shrink the input |
Four recursion programs exams love. Know them? Here are all four. Factorial stops at one. Fibonacci, f here, adds two calls. GCD stops when b is zero. Power stops at exponent zero. Remember. Find the base case. Then shrink the input.
This clip is from the full lesson: Recursion in Java — 8 minutes, with the tables, the quick answers and the whole lesson in text.
Useful for: ISC Class 11 Computer Science (868), ISC Class 12 Computer Science (868), ISC Class 12 Computer Science (868), Programming All levels Java
More KwickClips from this lesson
Where do waiting calls go?44 sec
Why does my recursion crash with StackOverflowError?41 sec
Can you reverse a word without a loop?41 secVoice-over is AI-generated; the script is written and checked by Kajal Ma'am. Confirm anything you plan around against your official board document. We never ask for a password or an OTP.