Recursive algorithms

Содержание и основные понятия

The recursive function contains a base case and transition to a smaller task. The answer is collected when the stack is folded back.
substance and practice
Grade 11
EGE No. 16
01
How it works.
Recursion solves the problem through a smaller version of the same problem. The correctness requires a base, a diminishing argument, and an understandable closing of the result.
Base.
An incident that returns an answer without a new call.
Transition.
A recursive challenge with an argument approaching the base.
Rolling.
After the base, the values return in reverse order.
Value.
One recursive call is often linear; two branches can provide an exponential number of challenges.
02
One example in execution
Start the short program and go over the lines. The visualiser only shows the code, current line, variables and output.
Recursive factorial for n >=0 has a base
n <= 1
and transition
n * factorial(n - 1)
If the argument is not diminished or the base is not within reach, Python will complete work with
RecursionError
For repeatable branches like Fibonacci, memo is used: the dictionary retains the already calculated values and removes the rework.
Algorithm map
Read from left to right, then run the code.
1
Start
2
Call f(3)
3
n <= 1?
4
No: call f(n-1)
5
Return the work and remove it
03
Remember
Check the base on the minimum allowed n.
Prove that every recursive path is approaching the base.
Don't apply naively hamstringed recursion to a big n without memo.
Syntax of this page
def f(n)
Determines a recursive function.
if base: return
The base case stops the branch of the recursion.
f(n - 1)
A recursive transition with a diminishing argument.
RecursionError
Exception with too deep a recursion or an impossible base.
dict.get(key, default)
In memoization, you read a saved answer or default value.
lru_cache
Functools decorator for memosis; use it after understanding the manual state.
print
Shows the final folded result.
global calls
Allows the function to change the name of the level of the module; apply only to the training path of the counter.
calls += 1
Increases the call meter by one.