Recursion Notes
What is Recursion?
● Recursion is a process using a function or procedure that is defined in terms of itself and
calls itself.
● The process is defined using a base case, a terminating solution to a process that is not
recursive,
● And a general case, a solution to a process that is recursively defined.
What are the benefits of Recursion?
● Recursive solutions can contain fewer programming statements than an iterative solution.
● The solutions can solve complex problems in a simpler way than an iterative solution.
Why are recursive solutions more beneficial than iterative solutions?
● Recursive solutions can contain fewer programming statements than an iterative solution.
● The solutions can solve complex problems in a simpler way than an iterative solution.
Name the problem that can occur when using recursion.
● stack overflow
Why may stack overflow occur?
● if recursive calls to procedures and functions are very repetitive, there is a very heavy use
of the stack, which can lead to stack overflow
State a disadvantage of using recursion
● When using recursive solutions, if recursive calls to procedures and functions are very
repetitive, there is a very heavy use of the stack, which can lead to stack overflow.
What is winding?
● process which occurs when a recursive function or procedure is called until the base case
is found.
What is unwinding?
● process which occurs when a recursive function finds the base case and the function
returns the values.
What is meant by a base case?
● a terminating solution to a process that is not recursive.
What is meant by a general case?
● a solution to a process that is recursively defined.
Explain how a compiler makes use of a stack when translating recursive programming code.
● The compiler must produce object code to
● …push return addresses / values of local variables onto a stack
● …with each recursive call // … to set up winding
● …pop return addresses / values of local variables off the stack …
● …after the base case is reached // … to implement unwinding.
State three essential features of recursion.
● Must have a base case/stopping condition
● Must have a general case
● … which calls itself (recursively) // Defined in terms of itself
● … which changes its state and moves towards the base case
● Unwinding can occur once the base case is reached.
Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion.
● A stack is a LIFO data structure
● Each recursive call is pushed onto the stack
● …. and is then popped as the function ends
● Enables backtracking/unwinding
● … to maintain the required order.
