Process¶
Recursion - General¶
Recursion (Latin recurrere – 'to run back') is an essentially endless process that contains itself as part or can be defined using itself. In computer science, recursion occurs whenever a function calls itself.
- Typical applications are divide-and-conquer algorithms and combinatorial problems
Recursion in Python¶
In Python, recursion is achieved by a function calling itself.
def recursive_function():
Statement1
recursive_function()
Example: Factorial¶
The factorial of a number is defined as the product of the natural numbers from 1 to n
def factorial_recursiv(x):
if x > 1:
return x * factorial_recursiv(x - 1)
else:
return 1
Warning: Infinite recursion¶
With recursive functions there is the same problem as with while loops: they can (theoretically) branch out forever!
Therefore, at least one path through the function should not be recursive.
Background: Stack Overflow Error¶
- The stack is a list that records which functions are currently being called
- This tells you where to return to when a function finishes
- In the case of infinite recursion, the list grows without bound
Background: Stack Overflow Errors¶
The stack is a list that records which functions are currently being called
This determines where to return to when a function finishes
In the case of infinite recursion, the list can grow without bound
Infinite recursion leads to stack overflow errors
It results in a hard crash of the program
Heap vs Stack¶
The stack is a region of memory in which function calls and their local variables are managed according to the LIFO principle (Last In, First Out). Each new function call is pushed onto the top of the stack and removed again when it finishes. If the stack becomes full, a stack overflow error occurs.
- For function calls
- LIFO principle
- Limited memory
The heap refers to a region of memory where variables are managed. The heap, in contrast to the stack, is not limited but grows dynamically with demand. Memory on the heap is managed in a FIFO-like manner and must be explicitly freed.
- For variables
- FIFO-like
- Dynamically sized (RAM)
Lesson Learned - Follow-Up¶
- Survey (Gain an overview): Skim through a topic to gain an overview
- Question (Questions): Note down questions about points you don’t understand.
- Read (Read): Read through your notes; highlight keywords; research the questions.
- Recite (Recite): Recapitulate each section (content, keywords, connections). Organize the material, e.g., with mind maps. Repeat what you’ve learned several times (flashcards).
- Review (Reflect): Mentally review the key points and answer your questions.
Mind Map¶
- Work from the inside out
- Reduces topics to individual terms
- A structure forms automatically
- Uses colors and symbols
- Creates connections between concepts
