Iterative versus recursive
The same calculation written with a loop or with recursive calls: equivalence, stack memory, repeated work, moving from one form to the other and how to choose.
- 25 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
Iteration: what is it?
Show the answer
Repeating a block of instructions with a loop, with variables that change on each pass until the calculation is done.
The loop keeps its state in a few variables, like
rinr = r * n; the recursive version keeps it in the parameters of each call.Which recursive function returns the same value as
ffor any integer n ≥ 1?
```python
def f(n):
r = 1
while n > 1:
r = r * n
n = n - 1
return r`def g(n): return 1 if n <= 1 else n * g(n - 1)def g(n): return 1 if n <= 1 else n + g(n - 1)def g(n): return 1 if n <= 1 else g(n - 1)def g(n): return 0 if n <= 1 else n * g(n - 1)
Show the answer
def g(n): return 1 if n <= 1 else n * g(n - 1)The loop multiplies
rby n, n - 1, …, 2 starting from 1: it is the factorial. The initialr = 1becomes the base case, andr = r * nbecomesn * g(n - 1). With+you add, withoutn *the result stays 1, and a base case of 0 wipes everything out.Any calculation written with a loop can be written with recursive calls, and the other way round: the two forms are …, but the recursive form takes up room on the ….
Show the answer
Any calculation written with a loop can be written with recursive calls, and the other way round: the two forms are equivalent, but the recursive form takes up room on the call stack.
To go from a recursive form to a loop, the parameters become variables updated on each pass. For complex structures, you may have to manage a stack yourself.
Stack overflow: what is it?
Show the answer
The error that occurs when too many function calls are nested at the same time and the memory area that holds them is full.
In Python, the interpreter stops sooner, on
RecursionError. In C or Java, the program is interrupted, with aStackOverflowErrorin Java.