Recursion
A function that calls itself: base case, call on a smaller problem, call stack, going down and coming back up, and the runaway recursion that ends in an error.
- 30 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Recursion: what is it?
Show the answer
A technique where a function calls itself to solve a smaller problem, of the same kind as the original one.
It is written in two parts: a case where the function answers directly, and a call on reduced data.
fact(4)relies onfact(3), which relies onfact(2).What does
fact(4)return?
```python
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)`241016120
Show the answer
24fact(4)is 4 ×fact(3), that is 4 × 3 × 2 × 1 ×fact(0)= 24. The values come back on the way up: 1, 1, 2, 6, then 24. Adding would give 10, and 120 isfact(5).A correct recursive function has a … that answers without a call, and each call works on a … problem, so as to get closer to it.
Show the answer
A correct recursive function has a base case that answers without a call, and each call works on a smaller problem, so as to get closer to it.
If either is missing, the chain of calls never ends: the base case cuts it, the shrinking of the problem guarantees it is reached.
Base case: what is it?
Show the answer
The case where the function returns its answer directly, without making a new call: it is what stops the chain of calls.
For the factorial,
fact(0)returns 1. Without this case, no call can ever return a value.