Recursion
Features of Recursion
What is Recursion?
Recursion is a highly effective programming technique where a function calls itself to solve a
problem or execute a task
Recursion doesn't rely on iterative loops. Instead, it uses the idea of self-reference to break
down complicated problems into more manageable subproblems
A recursive algorithm has three features:
o the function must call itself
o a base case - this means that it can return a value without further recursive calls
o a stopping base - this must be reachable after a finite number of times
How does recursion work?
In a recursive function, the function calls itself with a modified input parameter until it
reaches a base case — a condition that stops the recursion and provides the final result
Each recursive call breaks down the problem into more minor instances until it reaches the
base case
Example: Factorial calculation
Module Module1
Sub Main()
Dim result As Integer = factorial(5)
Console.WriteLine(result)
Console.ReadKey()
End Sub
Function factorial(ByVal n) 'Base case
If n = 0 Or n = 1 Then
Return 1
Else
'Recursive call with a smaller instance of the problem
Return n * factorial(n - 1)
End If
End Function
End Module
In this example, the factorial function calculates the factorial of a positive integer n
It does so by breaking down the problem into smaller instances, multiplying n with the
factorial of (n - 1) until it reaches the base case (n == 0 or n == 1)
Importance of a proper stopping condition
It is important to have a proper stopping condition or base case when using recursion
to avoid stack overflow errors which result in program crashes
If a recursive function does not have a stopping condition, it will continue to call itself
indefinitely, which can use up excessive memory and cause the program to malfunction
Designing a stopping condition
When creating a stopping condition, it's important to consider the problem being solved
Identify the easiest scenario where the function can provide a direct result. This scenario
should be defined as the base case, covering the simplest instances of the problem
By doing so, the function will be able to stop the recursion when those conditions are met
The difference between line 7 and the function declaration on line 1, is that num1 is
replaced with result + 1 so we'll need to set num1 equal to result + 1
Recursion: Benefits & Drawbacks
Programs can be written using either recursion or iteration - which one is used will depend
on the problem being solved
There are many benefits and drawbacks to using either, depending on the situation:
Recursion
Benefits Drawbacks
Concise - can often be expressed in a more concise way, especially for Performance - repeated function calls can be
structures like trees or fractals Memory intensive, leading to slower executio
Simple - simply stating what needs to be done without having to focus Debugging - recursive code can be much mor
on the how can make it more readable and maintainable track the state of the program
Limited application - not all problems are sui
recursive solutions
Iteration
Benefits Drawbacks
Performance - more efficient that recursion, less Complexity - can get very complex and use more lines of cod
memory usage. recursive alternatives
Less concise - compared to recursive alternatives, making the
Debugging - easier to understand and debug
understand
Wider application - more suitable to a wider range of
problems
Writing Recursive Algorithms
Here is a recursive algorithm for a simple countdown program written in Python to
countdown from 10 to 0
Module Module1
Sub Main()
Console.WriteLine(countdown_rec(10))
Console.ReadKey()
End Sub
Function countdown_rec(ByVal n) 'Base case
Console.WriteLine(n) 'output the starting number
If n = 0 Then 'stopping condition
Return 0
Else
Return countdown_rec(n - 1) 'recursive functional call
End If
End Function
End Module
10
9
8
7
6
5
4
3
2
1
0
Tracing Recursive Algorithms
Now lets trace the recursive algorithm we have just written to check what happens during
the execution of the program
Using a simple trace table we can trace the recursive function call
Function call print(n) countdown_rec(n -1)
countdown_rec(5) 5 4
countdown_rec(4) 4 3
countdown_rec(3) 3 2
countdown_rec(2) 2 1
countdown_rec(1) 1 0 (return)
Translate Between Iteration & Recursion
Recursive algorithms can be translated to use iteration, and vice versa
Let's look at the previous example recursive program and see how it would change to solve
the same problem but using an iterative approach
Recursive approach
Module Module1
Sub Main()
Console.WriteLine(countdown_rec(10))
Console.ReadKey()
End Sub
Function countdown_rec(ByVal n) 'Base case
Console.WriteLine(n) 'output the starting number
If n = 0 Then 'stopping condition
Return 0
Else
Return countdown_rec(n - 1) 'recursive functional call
End If
End Function
End Module
Iterative approach
Module Module1
Sub Main()
Console.WriteLine(countdown_rec(10))
Console.ReadKey()
End Sub
Function countdown_rec(ByVal n)
While n > 0
Console.WriteLine(n)
n = n - 1
End While
Return n
End Function
End Module
1. The recursive function call on line 05 has been replaced with a while loop (line 02) which
checks if n > 0
2. Using an iterative approach we use exactly the same amount of code (6 lines) BUT...
o less memory would be used (increased performance)
o easier to debug
