Recursion

Question 1

Recursive Programs

Answer 1

 Recursive programs
⚫ Recursion creates an alternative technique for us to use when we want
to ‘loop’ over a set of instructions.
⚫ Any iterative algorithm can be written using recursion instead.
⚫ Many of the algorithms we write can be implemented more elegantly using recursion than iteration…
⚫ Recursion lends itself to processing where a task can be represented as a finite nested model of itself.
⚫ There are many applications of this in nature, and hence in CS (which spends most of its existence trying to model things in the real world!).
⚫ From the most basic to the sublime… math functions, data structure searches and sorts, AI, parallel processing…

Question 2

A simple recursive program

Answer 2

 Multiplication
⚫ Consider the humble unsigned integer multiply operation.
⚫ Imagine trying to implement this purely in software (no HW support)…
⚫ Remembering that a*b is just adding a to itself b times…
⚫ Or if you implement it recursively…

Question 3

Avoiding Infinite Recursive Loops

Answer 3

 Some golden rules to avoid infinite loops.
⚫ Ignore these only if you want to watch your program (and your fellow programmers’ heads) explode.

 ensure there’s a terminating case (i.e. part of the definition that doesn’t make a recursive call).

 ensure that the recursion is monotonic across a state space. Conceptually, this means it makes the problem smaller each time

 ensure that all parts of the definition eventually lead to the
terminating case

Question 4

Performance Implications 1

Answer 4

 Recall your Digital Systems lectures from last year…
⚫ What happens when you call a function/method to pass parameters and return values?

 Stack frame containing the Current PC + function parameters is pushed onto the system stack
 Function is executed
 Stack frame is popped from the stack
 Return value is pushed onto the stack
 Control is returned to the point at which function was called.

Question 5

Performance Implications 2

Answer 5

 Imagine what happens to stack in a recursive method…
⚫ One stack frame for each invocation is on the stack
⚫ One copy of each method’s local variables on the stack
⚫ Additional processing time associated with ACL checking on each method invocation…

 Recursive methods in Java generally:
⚫ Have a larger dynamic RAM footprint than iterative equivalents
⚫ Footprint grows linearly with number of invocations… known as stack explosion
⚫ Take longer to execute due to overheads in the JVM associated with method invocation, memory allocation.

So is it actually possible to have an infinite recursive loop?

Question 6

Types of Recursion

Answer 6

 Recursive programs are classified based on where in their execution the recursive call is made…

 Head Recursion
⚫ The first statement in a method is recursive

 Middle / Multi Recursion
⚫ One or more arbitrary statements in a method is recursive

 Tail Recursion
⚫ The final statement in a method is recursive.

Question 7

Efficiently using Recursion

Answer 7

 Tail Recursive methods can be optimised by your compiler to prevent stack explosion.
 As the only recursive call is at the end of the method, the compiler can rewrite the stack…
 That final ‘version’ of the method when it completes will no longer need its local variables
 The stack frame for the next call can safely replace the current one!

 Many languages perform this optimisation.
⚫ It can have huge effects on recursive processing of large data sets
⚫ Note: ‘safe’ languages often don’t support optimisation of mutual recursion – only self recursion.