Recursion in python is a programming technique in which a function calls itself repeatedly until a condition is met.
It is a way of solving problems by breaking them down into smaller, more manageable pieces that can be solved in a similar way.
In Python, recursive functions are defined similarly to regular functions but include one or more calls to themselves within their body.
Let’s understand recursion in python from its syntax.
def function():
#....
function()
#....
A recursive function is a function that calls Itself repeatedly until a certain condition is met.
As you can see in the example code above, a function()
is defined, and the same function is called in the function’s body.
In the above function function()
, #...
represents some other code.
It may be conditional if-else, loop, or maybe another function. For example:
def function():
#some code
if(condition):
#stop calling itsef
else:
function()
Understanding Recursion in Python with Visual Representation
This is the visual representation of recursion in python. It clearly shows how the recursion phenomenon works in python.
Some Example Programs on Recursion
Here are some example programs.
Python Program to Find Factorial of a Number using Recursion
The factorial of a number is the product of all positive integers up to that number. Here’s a recursive function that calculates the factorial of a number:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
In this example, the factorial
function is defined recursively. It takes a single argument (n
) and returns the factorial of that number.
If n
is zero, the function returns 1
, since the factorial of zero is one. Otherwise, the function multiplies n
by the factorial of n-1
.
Python Program to Compute the Fibonacci sequence with Recursion
The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding numbers.
Here’s a recursive function that computes the nth number in the Fibonacci sequence:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
Python Program to Reverse a String with Recursion
Here’s a recursive function that takes a string and returns the string in reverse order:
def reverse_string(s):
if len(s) == 0:
return s
else:
return reverse_string(s[1:]) + s[0]
Python Program to Find the GCD of two numbers with Recursion
The greatest common divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder.
Here’s a recursive function that finds the GCD of two numbers using the Euclidean algorithm:
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
Python Program to Calculate the Sum of a list with Recursion
Here’s a recursive function that takes a list of numbers and returns their sum:
def sum_list(lst):
if len(lst) == 0:
return 0
else:
return lst[0] + sum_list(lst[1:])
Python program to check if the string is palindrome or not with Recursion
Here’s a recursive function that checks whether a given string is a palindrome (i.e., reads the same backward as forward):
def is_palindrome(s):
if len(s) <= 1:
return True
else:
return s[0] == s[-1] and is_palindrome(s[1:-1])
Python Program to Find Minimum Value in a List Using Recursion
Here’s a recursive function that takes a list of numbers and returns the smallest value:
def min_value(lst):
if len(lst) == 1:
return lst[0]
else:
return min(lst[0], min_value(lst[1:]))
Python Program to Calculate Power of Number with Recursion
Here’s a recursive function that calculates the result of raising a number to a given power:
def power(base, exponent):
if exponent == 0:
return 1
elif exponent % 2 == 0:
return power(base, exponent/2)**2
else:
return base * power(base, exponent-1)
Python Program to Convert a Decimal Number to Binary
Here’s a recursive function that takes a decimal number and returns its binary representation:
def dec_to_bin(n):
if n == 0:
return ''
else:
return dec_to_bin(n // 2) + str(n % 2)
Python Program to Draw a Fractal Tree Using Turtle Graphics
Here’s a recursive function that uses the turtle
module to draw a fractal tree:
import turtle
def draw_tree(branch_length, t):
if branch_length > 5:
t.forward(branch_length)
t.right(20)
draw_tree(branch_length-15, t)
t.left(
When writing a recursive function, it’s essential to define the base case, which specifies the condition in which the function should return a value without making any further recursive calls.
It’s also important to ensure that the recursive calls move toward the base case so that the function doesn’t enter an infinite loop.
Finally, it’s essential to think carefully about the resources the recursive function uses, such as the stack, and ensure that it doesn’t use too many resources or cause a stack overflow.
Discover more from Python Mania
Subscribe to get the latest posts sent to your email.