Recursion in Python

Recursion is an approach to solve a problem which involves a function calling itself either directly or indirectly. Such a function is known as a recursive function.

Every recursive method must have a base case which would stop calling the function again and again indefinitely, because the function stack has a limit, which is platform dependent.

A Python program to print a string backwards using a recursive function.

def reverse(s, n):

    if n > 0:

        print(s[n], end = '')

        reverse(s, n - 1)

    elif n == 0:

        print(s[0])

s = input('Enter the string: ')

reverse(s, len(s) - 1)

A Python program to calculate a^b using a recursive function.

def power(a, b):

    if b == 0:

        return 1

    else:

        return a * power(a, b - 1)

a = int(input('a = '))

b = int(input('b = '))

p = power(a, b)

print('a to the power b: ' + str(p))

A Python program to find the Factorial using a recursive function.

def factorial(n):

    if n == 0 or n == 1:

        return 1

    else:

        return n * factorial(n - 1)

n = int(input('n = '))

f = factorial(n)

print('Factorial: ' + str(f))

A Python program to find the GCD using a recursive function.

def gcd(a, b):

    if b == 0:

        return a

    else:

        return gcd(b, a % b)

a = int(input('a = '))

b = int(input('b = '))

hcf = gcd(a, b)

print('GCD: ' + str(hcf))

A Python program to display Fibonacci Series using a recursive function.

def fibo(n):

    if n == 1:

        return 0

    if n == 2:

        return 1

    return fibo(n - 1) + fibo(n - 2)

n = int(input('Number of terms: '))

for i in range(1, n + 1):

    print(fibo(i), end = ' ')

print()

A Python program to perform Binary Search using a recursive function.

def search(myList, key, low, high):

    if low > high:

        return -1

    mid = (low + high) // 2

    if key == myList[mid]:

        return mid

    elif key < myList[mid]:

        return search(myList, key, low, mid - 1)

    else:

        return search(myList, key, mid + 1, high)

myList = [12, 23, 34, 45, 56, 67, 78]

key = int(input('Element to be searched: '))

index = search(myList, key, 0, len(myList) - 1)

if index >= 0:

    print(str(key) + ' is present at index ' + str(index))

else:

    print(str(key) + ' is not present')