Recursion Demystified: Think Recursively

In my experience, when most people especially beginners are presented with the concept of recursion, they react surprisingly as if the have been exposed to a new trick. Rather than embracing it is as a new programming concept or methodology,they overlook it and later becomes hard for them to write programs that require recursion. Recursion is a very useful technique in programming.It is a notion that can frequently be challenging especially for beginning computer science students because it nearly seems like circular reasoning. This articles seeks to demystify all it entails with practical examples enabling one to think recursively.

Recursion is the programmer's most important weapon. Curious to find out how or why?...Read through this article.

Note:All the code written in this article is implemented using python programming language.

Prerequisite

• Introduction to programming concepts
• Python basics

What is recursion?

In computer science, recursion is mathematical and programming technique using function or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.

Simply stating, it is the process of defining something in terms of itself. A concept of well-defined self-reference.

What is recursion in Python

In Python, recursion is the process of a function calling itself directly or indirectly. It enables one to find a solution to a problem by breaking it into smaller and simpler steps. We keep breaking it down until we reach a problem that is small enough to be solved easily.

Why use Recursion

• Shorter and easier code to write than an iterative code
• Useful for tasks composed of similar subtasks - most useful for tasks that can be defined in terms of similar subtasks.
• Loops are also converted into recursive functions when they are compiled or interpreted.
• Using recursion, it is easier to generate the sequences compared to iteration
• Efficient Sort and Search: Recursion is especially useful for Python data science as it is the foundation of popular sort algorithms like mergesort.
• In some cases, it's more natural to “think recursively”. Recursion is the clearest, simplest way to solve problems in data structures like trees where a recursive structure is simple to understand.
• There are some problems which are quite difficult or impossible to solve with Iteration.

Properties of Recursion:

• Performing the same operations multiple times with different inputs.
• In every step, we try smaller inputs to make the problem smaller.
• Base condition is needed to stop the recursion otherwise infinite loop will occur.

Types of Recursion

1. Direct

Direct recursion is When a function calls itself directly, from within its body.

• A method calling itself is considered to be direct recursion

def recursion():
recursion()

1. Indirect

Indirect recursion is when a function calls some other function, which in turn calls its caller function again.
A method can invoke another method which invokes another etc., until eventually the original method is invoked again. This is what indirect recursion is all about. It is more difficult to trace and debug.

def func1():
func2()

def func2():
func1()

Recursive Function Format

Comprises of two main parts:

• Base case When using recursion, we have to write sensible code that instructs the compiler, when to stop the process otherwise it will run endlessly. However, writing such a code in Python returns an error to prevent this. Sample error:

RecursionError: maximum recursion depth exceeded...

Therefore, A Base Case is a case, whose result is known or predetermined, without any recursive calling.

• Recursive case It computes the result by making recursive calls to the same function, but with the inputs decreased in size or complexity.

1. Base case (When to stop)
   The base case is where all further calls to the same function stop, meaning that it does not make any subsequent recursive calls.
   📌NOTE:📌 The base case in a recursive function, MUST BE REACHABLE!

2. Recursive case (call ourselves)
   The recursive case is where the function calls itself repeatedly until it reaches the base case. The desired state has not been reached and the function enters another recursive step.

Python Syntax of a Recursive Function

def RecursiveFunction() :
  # Base Case
  if <baseCaseCondition> :
    <return some base case value>

  # Recursive Case
  else :
    <return(recursive call and any other task)>

Iterative Vs. Recursive

Definition
Recursion refers to a situation where a function calls itself repeatedly until a base condition is satisfied, at which point further recursive calls stop.

Iteration refers to a situation where some statements are executed again and again using loops until some condition is satisfied.

Application
Recursion is a process because is always called on a function. Used with functions.

Iterative code is applied to variables. It is a set of instructions that are called upon repeatedly. Used with loops.

Program Termination
Terminates when the base case becomes true. Recursive code terminates when the base case condition is satisfied.

Terminates when the condition becomes false. Iterative code either runs for a particular number of loops or until a specified condition is met.

Code Size
Smaller code size. Recursive code is smaller in length and neater.

Larger code size. Iterative code is usually extensive and cluttered.

Overhead Time
Recursive code has an overhead time for each recursive call that it makes.

Iterative code has no overhead time.

Speed
Recursive code is slower than iterative code, since it not only runs the program but must also invoke stack memory.

Iterative code has a relatively faster runtime speed.

Stack Utilization
Recursion uses a stack to store the variable changes and parameters for each recursive call. Every recursive call needs extra space in the stack memory.

Every iteration does not require any extra space. Iterative code does not use a stack.

Disadvantages of recursion

• It is slower as compared to iteration.
• Hard to debug - Logical but difficult to find the error, if any exists.
• Recursion is expensive in both memory and time.It requires extra storage space this is because, for every recursive call, separate memory is allocated for the variables.
• Recursive functions often throw a Stack Overflow Exception when processing or operations are too large.
• Though it looks simple, it is sometimes hard to make the algorithms using recursion

NB: When using recursion, you should be very careful as it can be quite easy to slip into writing a function which never terminates, or one that uses excess amounts of memory or processor power

📌TIP:📌 You can find out what Python’s recursion limit is with a function from the sys module called getrecursionlimit()

from sys import getrecursionlimit
getrecursionlimit()

Output: 1000

To change the limit:

from sys import setrecursionlimit
setrecursionlimit(2000)
getrecursionlimit()

Output: 2000

You can set it to be pretty large, but you can’t make it infinite.

Recursion Examples

1. Calculate Factorial _Question: Write a program and recurrence relation to find the Factorial of n where n>2 . _

def factorial(n):
    # base case
    if x == 1:
        return 1
    # recursive case
    else:
        return x * factorial(x-1)

Time complexity: O(2n).

Auxiliary Space: O(n)

Tail-Recursion

It is a unique form of recursion, where the function calls itself at the end.

Recursive methods are either:

1. Tail recursive
2. Non-tail recursive

Tail recursive methods have recursive call as the last statement in the method.

Recursive methods that are not tail-recursive are called non-tail recursive

Why Tail Recursion ?

It is important to have tail-recursive methods because:

• The amount of information that gets stored during computation is independent to the number of recursive calls.
• Some compilers can produce optimized code that replaces tail recursion by iteration hence saving the overhead cost of the recursive calls
• Tail recursion is important in languages like Prolang and functional languages like Clean,Haskell, Miranda and SML that do not have explicit loop constructs (loops are simulated by recursion)

Finding the sum of numbers using tail recursion

def sum(n,last=0):
    if(n<=0):
        return last
    return sum(n-1,n+last)

sum(3)

Output: 6

Conclusion

Recursion is a great technique that allows for programs whose correctness can be easily verified without losing performance, but it forces programmers to adopt a fresh perspective on their craft. The majority of programming introductions concentrate on imperative languages and methodologies because imperative programming is frequently a more natural and intuitive beginning point for novice programmers. Recursive programming, however, offers the programmer a superior approach to organize code in a way that is both maintainable and logically consistent as systems grow more complicated.

Recursion is a key concept and a crucial part in every developer's skillset. It often takes up a large portion of interview questions at coding interviews and are essential for dynamic programming questions.

📌TAKEAWAY:📌
Most Common Recursion Applications

• Invert an Array
• Fibonacci Sequence
• Sum from 1 to n
• 0-1 knapsack problem
• Balanced parentheses question
• Convert tree to a doubly linked list
• Reverse a stack
• Reverse a Linked List
• Print all leaf nodes of a Binary Tree from left to right
• Lowest common ancestor
• Remove spaces from a string
• Towers of Hanoi

✨About Me:✨

Hey there, My name is Emma Donery, currently, a Software Engineer building data platforms. My interests include data analysis, data engineering, ui/ux design, competitive coding, and Machine Learning. Please feel free to connect with me through my socials. I always love to have a chat with similarly minded people.

Linkedin | Twitter | Instagram | Facebook | Github

Hope you enjoyed reading this article. Happy learning!