View source for A-level Computing/AQA/Paper 1/Fundamentals of programming/Recursion

<NOINCLUDE>
{{CPTPageNavigationP1|
 | Prev = Stack Frames
 | Next = Paradigms Intro}}
{{DISPLAYTITLE:Programming Concepts: Recursive Techniques}}
</NOINCLUDE>

{{Dbox|[[wiktionary:recursion|Recursion]]|Defining a sub routine in terms of itself.}}
Recursion is a key area in computer science that relies on you being able to solve a problem by the cumulation of solving increasingly smaller instances of the same problem.

[[File:Droste.jpg|thumb|A visual form of recursion known as the ''[[w:Droste effect|Droste effect]]''. The woman in this image is holding an object which contains a smaller image of her holding the same object, which in turn contains a smaller image of herself holding the same object, and so forth.|center]]

An example of recursion in a name is the [[w:GNU|GNU]] Operating System, you might well ask what GNU stands for:
:GNU = GNU is Not [[w:Unix|Unix]]
Wait a minute, they have defined the name by restating the name!:
::::::GNU
:::::GNU is Not Unix
::::GNU is Not Unix is Not Unix
:::GNU is Not Unix is Not Unix is Not Unix
::GNU is Not Unix is Not Unix is Not Unix is Not Unix
:[[w:Ad infinitum|ad infinitum]]
Luckily for us, with computer code our recursion should tend towards an end as we are solving increasingly smaller instances of the same problem, we should be tending towards an end. With the GNU example the name always remains the same size, but with the following example there is an end:

{{CPTExample|title=Example: A recursive story}}
<syntaxhighlight lang="javascript">
function revise(essay) {
  read(essay);
  get_feedback_on(essay);
  apply_changes_to(essay);
  revise(essay) unless essay.complete?;
} 
</syntaxhighlight><ref>thesecretmaster on StackExchange https://cseducators.stackexchange.com/questions/17/analogy-for-teaching-recursion</ref>
Which is pseudocode to describe the process of revising an essay, the revision process involves reading the essay, getting feedback, applying the changes, then revising the slightly better essay. You keep doing this until the essay is complete.
{{Robox/Close}}

Let's take a look at some computer science examples

== Factorial example ==
A classic computer example of a recursive procedure is the function used to calculate the [[w:factorial|factorial]] of a [[w:natural number|natural number]]:
:<math>n ! = n \times (n-1) \times (n-2) \times ... \times 1</math>
For example:
:<math>3 ! = 3  \times  2  \times  1 = 6  \ </math>
:<math>5 ! = 5  \times  4  \times  3  \times  2  \times  1 = 120  \ </math>
:<math>10 ! = 10  \times  9  \times  8  \times  7  \times  6 \times 5 ! = 3628800  \ </math>
Did you notice what I did with the final solution? Instead of writing 5 * 4 * 3 * 2 * 1, I used 5! which [[wiktionary:elicit|elicits]] the same result. Looking back our definition of why recursion is used, we seem to solve big problems by solving smaller instances of the same problem, so factorials are ripe for recursion:
 10! = 10 * 9!
 9! = 9 * 8!
 8! = 8 * 7!
 7! = 7 * 6!
 6! = 6 * 5!
 5! = 5 * 4!
 4! = 4 * 3!
 3! = 3 * 2!
 2! = 2 * 1!
 1! = 1
As we can see, each n! is the product of n * (n-1)!. In summary:
:<math> \operatorname{fact}(n) =
 \begin{cases}
 1 & \mbox{if } n = 1 \\
 n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 1 \\
 \end{cases}
</math>

{| class="wikitable"
|-
! [[Pseudocode]] (recursive):
|-
|
 '''function''' factorial is:<br />
 '''input''': integer ''n'' such that ''n'' >= 1<br />
 '''output''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
 <br />
     1. if ''n'' is >= 1, '''return''' [ ''n'' × factorial(''n''-1) ]
     2. otherwise, '''return''' 1
 <br />
 '''end''' factorial
|}
Now let's have a look at how we would write code to solve this:
<syntaxhighlight lang="vb">
function factorial(ByVal n as integer)
  if n >= 1 then
    return n * factorial(n-1) 'recursive call
  else
    return 1
  end if
end function

sub main()
  console.writeline(factorial(10))
end sub
</syntaxhighlight>
It looks very simple and elegant. But how does it work?

[[File:CPT-Recursion-Factorial-Code.svg|center|Diagram of how recursion calculates factorial(4)]]

Let's build a trace table and see what happens. This trace table will be different from the ones that you have built before as we are going to have to use a stack. If you haven't read up on [[#stacks|stacks]] you must do so before continuing:

{| class="wikitable"
|-
! Function call !! n !! Return Line 
|-
| 1 || 4 || 
|}
All is going well so far until we get to line 3. Now what do we do? We'll soon have two values of n, one for Function call 1 and one for Function call 2. Using the trace table as a stack (with the bottom of the stack at the top and the top of the stack at the bottom) we'll save all the data about the function call including its value of n and make note of what line we need to return to when we have finished with factorial(3).

{| class="wikitable"
|-
! Function call !! n !! Return Line 
|-
| 1 || 4 || 3
|-
| 2 || 3 ||
|}
We now have a similar situation to before, let's store the return address and go to factorial(2)
{| class="wikitable"
|-
! Function call !! n !! Return Line 
|-
| 1 || 4 || 3
|-
| 2 || 3 || 3
|-
| 3 || 2 || 
|}
We now have a similar situation to before, let's store the return address and go to factorial(1)
{| class="wikitable"
|-
! Function call !! n !! Return Line !! Return Value
|-
| 1 || 4 || 3 ||
|-
| 2 || 3 || 3 ||
|-
| 3 || 2 || 3 ||
|-
| 4 || 1 || || 1
|}
Now we have another problem, we have found an end to the factorial(1). What line do we go to next? As we are treating our trace table as a stack we'll just pop the previous value off the top and look at the last function call we stored away, that is function call 3, factorial(2), and we even know what line to return to, line 3:
<syntaxhighlight lang="vb">
return 2 * factorial(1)
</syntaxhighlight>
We know that factorial(1) = 1 from the previous returned value. Therefore factorial(2) returns 2 * 1 = 2
{| class="wikitable"
|-
! Function call !! n !! Return Line !! Return Value
|-
| 1 || 4 || 3 ||
|-
| 2 || 3 || 3 ||
|-
| 3 || 2 || 3 || 2
|-
| <s>4</s> || <s>1</s> || || <s>1</s>
|}
Again we'll pop the last function call from the stack leaving us with function call 2, factorial(3) and line 3.
<syntaxhighlight lang="vb">
return 3 * factorial(2)
</syntaxhighlight>
We know that factorial(2) = 2 from the previous returned value. Therefore factorial(3) returns 3 * 2 = 6
{| class="wikitable"
|-
! Function call !! n !! Return Line !! Return Value
|-
| 1 || 4 || 3 ||
|-
| 2 || 3 || 3 || 6
|-
| <s>3</s> || <s>2</s> || <s>3</s> || <s>2</s>
|-
| <s>4</s> || <s>1</s> || || <s>1</s>
|}
Again we'll pop the last function call from the stack leaving us with function call 1, factorial(4) and line 3.
<syntaxhighlight lang="vb">
return 4 * factorial(3)
</syntaxhighlight>
We know that factorial(3) = 6 from the previous returned value. Therefore factorial(4) returns 4 * 6 = 24
{| class="wikitable"
|-
! Function call !! n !! Return Line !! Return Value
|-
| 1 || 4 || 3 || 24
|-
| <s>2</s> || <s>3</s> || <s>3</s> || <s>6</s>
|-
| <s>3</s> || <s>2</s> || <s>3</s> || <s>2</s>
|-
| <s>4</s> || <s>1</s> || || <s>1</s>
|}
We reach the end of function call 1. But where do we go now? There is nothing left on the stack and we have finished the code. Therefore the result is 24.

== Fibonacci number example ==
[[File:Fibonacci blocks.svg|thumb|center|Fibonacci numbers are found in nature and have fascinated mathematicians for centuries]]
Another good example is a method to calculate the [[w:Fibonacci numbers|Fibonacci numbers]]. By definition, the first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two.:
:<math>0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;</math>
For example, take the 6th number, 5. This is the sum of the 5th number, 3, and the 4th number, 2.

In mathematical terms, the sequence ''F<sub>n</sub>'' of Fibonacci numbers is defined by the recursive statement
:<math>F_n = F_{n-1} + F_{n-2},\!\,</math>
with the first two values being
:<math>F_0 = 0 \quad\text{and}\quad F_1 = 1.</math>

Let's try and create a code version of this:
{| class="collapsible collapsed" style="border: none;"
| '''Answer:'''
! colspan="2" | &nbsp;
|-
| colspan="2" | 
<syntaxhighlight lang="vbnet" line>
function fib(n as integer)
  select case n
    case 0
      return 0
    case 1
      return 1
    case else
      return fib(n-1) + fib(n-2)
  end select
end function
</syntaxhighlight>
| &nbsp;
|}

== Recursion summary ==
Recursion does have some issues though, consider how much data we had to store on the stack for just 4 function calls. If we were to perform 1000, the memory used would be incredibly large.

{{Plus|Recursion can produce simpler, more natural solutions to a problem}}
{{Minus|Recursion takes up large amounts of computer resources storing return addresses and states}}

{{CPTExercise|title=Exercise: Recursion}}
{{CPTQuestion|Define recursion:}}
{{CPTAnswer|Defining a sub routine in terms of itself}}
{{CPTQuestionTab}}
Give the output of the following recursive function call recur(6):
<syntaxhighlight lang="vbnet">
function recur(ByVal n as integer)
  console.writeline(n)
  if n > 0 then
    recur(n-1)
  else
    return 0
  end if
end function
</syntaxhighlight>
{{CPTQuestionTabEnd}}
{{CPTAnswerTab}}
 6
 5
 4
 3
 2
 1
 0
{{CPTAnswerTabEnd}}
{{CPTQuestionTab}}
Give the output of the following recursive function call recur(4):
<syntaxhighlight lang="vbnet">
function recur(ByVal n as integer)
  if n > 0 then
    recur(n-1)
  else
    return 0
  end if
  console.writeline(n)
end function
</syntaxhighlight>
{{CPTQuestionTabEnd}}
{{CPTAnswerTab}}
 1
 2
 3
 4
{{CPTAnswerTabEnd}}
{{CPTQuestionTab}}
Give the output of the following recursive function call recur(6):
<syntaxhighlight lang="vbnet">
function recur(ByVal n as integer)
  if n <= 10 then
    recur(n+1)
  else
    return 0
  end if
  console.writeline(n)
end function
</syntaxhighlight>
{{CPTQuestionTabEnd}}
{{CPTAnswerTab}}
 10
 9
 8
 7
 6
{{CPTAnswerTabEnd}}
{{CPTQuestion|Draw a trace table for the following recursive function}}
{{CPTAnswerTab}}
{{CPTAnswerTabEnd}}
{{CPTQuestion|Name one benefit and one drawback of recursive solutions:}}
{{CPTAnswerTab}}
* Recursion can produce simpler, more natural solutions to a problem
* Recursion takes up large amounts of computer resources storing return addresses and states
{{CPTAnswerTabEnd}}
{{Robox/Close}}
{{BookCat}}

==References==
{{Reflist}}