IT1815 Recursion Types

Study Notes

Recursion Fundamentals

Recursion involves a function calling itself to resolve problems, creating a method of solution.
Direct recursion occurs when a method directly calls itself.
Indirect recursion happens when a method invokes another method that eventually leads back to the original method.
Infinite recursion occurs when the function fails to meet a stopping condition, resulting in excessive function calls.

Elements of a Recursive Algorithm

Base case: A condition that terminates the recursion.
Change of state: Data within the algorithm must be modified to progress towards the base case.
Recursive call: The function must invoke itself to continue the recursion.

Types of Recursion

Linear recursion: The function calls itself once per invocation, e.g., calculating factorials.
Tail recursion: The recursive call is the last operation executed in the function, e.g., finding the greatest common divisor (GCD) of two integers.
Binary recursion: The function calls itself twice during its execution, e.g., generating the Fibonacci series.
Mutual recursion: A pair or group of functions calls each other, e.g., checking the parity (even or odd) of an integer.

Recursion vs. Iteration

Recursion terminates upon reaching a base case, while iteration ends when a condition becomes false.
Each recursive call consumes additional memory, potentially leading to stack overflow in cases of infinite recursion.
Iteration does not create extra memory space and could theoretically result in an infinite loop without exhausting memory.
Recursive solutions may provide clearer formulations for certain problems compared to their iterative counterparts.

Description

Explore the fundamentals of recursion in programming, focusing on linear recursion where a function calls itself once with each invocation. This quiz will test your understanding of how recursion works and its applications, such as calculating factorials.