Introduction
Recursion is often regarded as the one of the most complex concepts to understand in computer programming. IMHO, recursion is the “building block” of Functional programming, creating highly used data structures like Tree and an elegant way of writing code in general. So in this blog I’ll try to go through the basics and later solve a few problems to explain the concept in a better way. So, let’s get started!
What is Recusion
Recursion is a methodology of problem solving, where we get the solution of a problem by breaking it down to subproblems and keep breaking it till we reach a point where we can’t break it any further (also known as base condition). Once base condition is reached, we handle it then start returning the solution of the subproblem state that we are in, to the caller subproblem state (i.e the parent).
Hence, this way we can solve the overall problem, by solving the subproblems.
This is implemented by writing a function that calls itself, with a subset of problem set passed as argument each time, and hence keep breaking the problem.
Applications of Recursion
 Dynamic Programming
 Divide and Conquer
 Backtracking
 Tree traversal
Some problems on recursion
Now let’s solve some problems based on recursion, because often examples are best way to understand a concept.

Write a recursive function to print all numbers from N to 1 for a given number N.
def printN(N): if N == 0: return print(N) printN(N1) N = int(input("Enter N:")) printN(N)
In the above code, we pass number N by subtracting 1 from it each time, as argument to the function
printN
and it keeps printing it, untill it hits thebase condition
when N becomes equal to 1.This is also the case of
tail recursion
since we are performing some operation (in this case printing) before we recursively call the funtionprintN
. Sotail recursive
functions are those functions in which recursive calls are last thing that happens in the function.Tail recursion
is similar toloop
.
If we wanted to print 1 to N, then we would placeprint
after the recursive call, so that the function stack reaches the based condition whenN == 1
, then starts performing the operations (here printing) as stored in the function stack. This is calledhead recursion
. Inhead recursion
state is saved before making next call.def print_one_to_n(N): if N == 0: return print_one_to_n(N1) print(N)
Tail recursion
is faster thanhead recursion
because of a concept calledtail call elimination
(or Tail Call Optimization), in which the compiler essentially converts the recursion to a loop.Quick sort
uses tail recursion, hence is faster thanMerge sort
.Hence, making the above
print_one_to_n
function a tail recursive one by this way:def print_one_to_n(n,i=1): if n == 0: return print(i) print_one_to_n(n1,i+1)

Write a recursive function to check if a string is palindrome or not.
def palindrome(s): if len(s) <= 1: return True if s[0] != s[1]: return False return palindrome(s[1:len(s)1])

Write a recursive function to calculate the
nth
number in the Finonacci sequence.def fib(n): if n <= 1: return n return fib(n1)+fib(n2)
In the above solution it is important to analyse the recursion. Let’s try to understand this by taking example if
fib(5)
i.e 5th element in the Fibonacci sequence. When we callfib(5)
it recursively makes call tofib(4)
thenfib(3)
thenfib(2)
then hits the base condition when it callsfib(1)
as whenn<=1
fib returnsn
i.e 1 in this case.Now the control goes back to
fib(2)
when it recursively makes call tofib(0)
which is again a base condition and returns 0. So,fib(2)
returns1+0
back tofib(3)
whenfib(3)
will further make recursive call tofib(1)
which return 1. Hencefib(3)
returns1+1
back tofib(4)
. Nowfib(4)
makes another recursive call tofib(2)
which recursively callsfib(1)
andfib(0)
to essentially returns1+0
, hencefib(4)
returns2+1
tofib(5)
. Nowfib(5)
recursively makes call tofib(3)
which upon makes further calls would essentially return(1+0)+1
i.e 2. So, finallyfib(5)
returns3+2
back to the caller, which is the 5th element in the Fibonacci sequence.
(image courtesy mycodeschool, which has arguably the best videos on DSA on the entire internet) 
Write a recursive function to find the sum of the digits of a number.
def sum_of_digits(n,sum): if n <= 0: return sum sum += n %10 return sum_of_digits(n//10,sum)