By Tannyexy

Recursion 1
Definition: Recursion is when a procedure calls itself.
 Remember repetition, recursion is a special type of repetition where function calls itself and it
uses the result from its previous function’s results.
 This is in case that the first f(x) returned 7 then the next call will use 7 to solve a task.
Example

How a function call itself. If you still remember how to call a function.
We use its name then provide a parameter
e.g 𝒇(𝟐). The name of the function is f and
Function F(ByVal x As Integer)
the parameter is 2.

Return F(x)

So when a function calls itself it goes back to the

function. A function calling itself

Example: Take the code as the function

Function F(ByVal x As Integer)
So as you can see the program is going back to itself,
Return F(x)
acting as if it is repeating. The code returning as it was
before.
Function F(ByVal x As Integer)

Return F(x)

Function F(ByVal x As Integer)

If this type of repetition continues the program falls into an
Return F(x)
error called Stack Overflow Error.

So to stop the program from continuing with the repetition Function F(ByVal x As Integer)
endlessly,
Return F(x)
1. Make it call itself using either an increment or
decrement of the parameter e.g 𝑓( 𝑥 + 1) 𝑜𝑟 𝑓(𝑥 −
1), to enable it to change the value of 𝑥 .
2. Make it select from your options to choose to return
a different value or call the function using a known
value that 𝑥 will become, for example: if 𝑥 will
change to 5 then do the following

If x = 5 Then
Return 5 Note: In case that our function is f(x) and the
Else function calls itself using a different
Return F(x + 1)
End if parameter. This different parameter becomes
the new value of x. for example:

1|P a g e F(x)  f(3)  x = 3

 By Tannyexy

 Recalling sequences in mathematics. Find a sequence of numbers from the function

below

Solving this in Mathematics

+1

Write down the sequence from the function above where n = 1 up to where n = 10

Solution
 since it is a sequence you start substituting numbers
for n e.g 1,2,3,4…. but you continue from n = 1
 so at this point you substitute 𝑼𝟏 and replace it with
+1 +1
the value of 𝑼𝟏
+1  You continue doing the same until n is equal to 10

+1 +1

1 +1

+1 +1

+1

+1 +1

+1

……………… Skipped some steps ………………

So at you will see that so the sequence becomes ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

2|P a g e
 By Tannyexy

 If you look carefully at the above problem, you will see that every time the value of n changes
the function with the new calls the previous function that is in its expression.

Example
Calling the previous
+ 1 when n = 1 it becomes + 1 which is the same as +1 function

+ 1 when n = 2 it becomes + 1 which is the same as +1

 So now you get the idea of what recursion does. In programming the calling of the previous
function is the same but what is different is what happens to n. The above n increases in value
but in programming it decreases in value.

Application in Programming

Question 1

1. Write a program that returns the Fibonacci sequence up to the 10th term. The function is
𝑓(𝑥 − 1) + 𝑓(𝑥 − ) (10) Marks

Solution Code and Interface

Function F(ByVal x As Integer)

If x <= 0 Then

Return 0

ElseIf x = 1 Then

Return 1

Else

Return F(x - 1) + F(x - 2)

End If

End Function

Private Sub Button1_Click() Handles [Link]

For i = 0 To 9
If [Link] <> Nothing Then
[Link] &= " , "
End If
[Link] &= F(i)
Next

End Sub

3|P a g e
 By Tannyexy

Example Question

𝑼𝒏 𝑼𝒏 𝟏 +𝟏 𝒘𝒉𝒆𝒓𝒆 𝑼𝟏 𝟎
Write a program to display the sequence from the function above where n = 1 up to
where n = 10

Solution Code and Interface

Function U(ByVal n As Integer)

If n = 1 Then

Return 0

Else

Return U(n - 1) + 1

End If

End Function

Private Sub Button1_Click() Handles [Link]

For i = 1 To 10
If [Link] <> Nothing Then
[Link] &= " , "
End If
[Link] &= U(i)
Next

End Sub

4|P a g e
 By Tannyexy
General explanation of the above solution
1. First explanation is for the function
 Note that it’s only code explanation.
 Note that the shaded parts are points being executed by the program.

 The grey part is the name of the function e.g

Function U(ByVal n As Integer) 𝑼𝒏
 The green part is the same as setting 𝑼𝟏 𝟎
If n = 1 Then
This is because when n = 1 ,
Return 0 𝑼𝟏 𝑠 𝑜𝑢𝑙𝑑 𝑏𝑒 𝑒𝑞𝑢𝑎𝑙 𝑡𝑜 𝟎
 So every time when you want the first value of
Else 𝑈𝑛 you should write a similar code but you
Return U(n - 1) + 1 just change the values of n = 1 and Return 0.
For example
End If

End Function

 The pink part is the function it self 𝑼𝒏 𝟏 + 𝟏

Function U(ByVal n As Integer)  So every time you want to write a code using a
recursive approach that is the way you write the
If n = 1 Then code for the given function.
 For example:
Return 0

Else

Return U(n - 1) + 1

End If

End Function

2. Explanation on what happens to n.

When n is introduced into the function it will be >= 1. Let’s say n
Function U(ByVal n As Integer) was 3. The if statement is not executed but the program goes for
else statement and it calls itself.
If n = 1 Then
n-1 When the else statement is executed the program stores 𝑼𝒏 𝟏 + 𝟏
Return 0 in a Call Stack and takes (n – 1) and make it the new value of n like
Else as pointed. In this case (n-1) = (3 - 1) so the new value n = 2. The
program then starts to execute the function. The process repeats
Return U(n - 1) + 1 until the value of n becomes 1. When the value of n is 1 ,the
program start calling back the functions stored in the Call Stack and
substituting the values using a method explained in page 2
5|P a g e
 By Tannyexy

3. Explanation of calling the function.

 The yellow part is the one that is going to change
For i = 1 To 10 the values that are going to be used as
If [Link] <> Nothing Then parameters and repeats the whole process.
[Link] &= " , "
End If  The pink part check if there is data in the textbox,
if so it then add a comma on the data e.g if there
[Link] &= U(i) is 0 in the textbox it makes it 0 ,
Next
 The green part calls the function and inserts
parameters and since a function returns a value it
stores the value in the textbox by adding it into
the textbox.

Practice question
Write a program that accepts the number of terms a user want to be displayed from the function below. The
program should display the sequence of the terms in descending order. For example: 10 , 9, 8 , 7 …….

𝑼𝒏 𝟑(𝑼𝒏 𝟏 + 𝟒) + 𝟏𝟎 𝒘𝒉𝒆𝒓𝒆 𝑼𝟎 𝟏 [15 Marks]

Sequence : ……… 1816 , 601 , 196 , 61 , 16 , 1

Solution  Code and Interface

Function U(ByVa l n As I nteger)

If n = 0 T hen

Return 1

Els e

Return 3 * (U( n - 1) + 4) + 1

End If

End Func tion

Private Sub But ton1_Cli ck() Ha ndles Bu tton1.C lick

Dim a As In teger
Try
a = Te xtBox2.T ext

For i = a To 0 Step - 1
If TextBox [Link] <> Nothi ng Then
TextBo [Link] &= " , "
En d If
Te xtBox1.T ext &= U(i)
Next

Cat ch ex A s Except ion

MsgBox ("Please enter a number of ter ms")
End Try
End Sub

6|P a g e
 By Tannyexy

Madanaime: Contact: 0771936890 /0718830036

Email: tanakasteven450@[Link]
Email: tanakasteven450@[Link]

7|P a g e