Python Recursive Function [Interview Question]

by

Introduction

In this tutorial, we will look at the Python recursive function problem which is asked by many companies in interviews. Recursive functions are one of the most important feature in any programming language. It allows us to optimize out code if there is repetitive task involved. We will look at a very common yet important coding problem which is mostly asked by many companies in the interview. Let’s get started.

 

Python Recursive Function [Interview Question]

Recursive Function Overview

In Python, a recursive function is a function  that calls itself during its execution. Recursive functions are a powerful and elegant way to solve problems that can be broken down into smaller, similar subproblems. They are widely used in programming and are particularly suited for tasks like tree traversal, mathematical calculations and problems that exhibit a recursive structure.

There are many usage of recursive function. Some of them are:

  • Mathematical Calculations
  • Tree and Graph Traversal
  • Divide and Conquer
  • Backtracking
  • Dynamic Programming
  • Complex Data Structure

 

Python Recursive Function [Interview Question]

Also read: How to Find Wi-Fi Password in Windows: [2 Easy Methods]

Problem Statement:

Write a Python function that efficiently calculates the result of raising an integer ‘a’ to the power of another integer ‘b’. Implement the function using a divide-and-conquer approach to optimize the computation of exponentiation. The function should handle both positive and zero exponents and return the correct result.

 

Solution:

def power(base, exponent):

    if exponent == 0:
        return 1

    # Calculate the result for half of the exponent
    half_power = power(base, exponent // 2)

    # If the exponent is even, return the square of half_power
    if exponent % 2 == 0:
        return half_power * half_power

    # If the exponent is odd, return half_power squared times the base
    else:
        return half_power * half_power * base

result = power(3, 5)
print(result)
OUTPUT
PS C:\Users\linuxnasa\Desktop\python-project> python .\recursive-func.py
243

 

Explanation:

1.  The ‘func’ function takes two arguments, ‘a’ and ‘b’.
2.  If ‘b’ is equal to 0, it returns 1, which represents the base case for exponentiation.
3.  Otherwise, it recursively calculates ‘temp’ by calling func(a, b//2), effectively halving the value of ‘b’.
4.  It then checks if ‘b’ is odd (b % 2 == 0), if so, it returns ‘temp*temp*a’ (raising ‘a’ to the power of ‘b’)
5.  If ‘b’ is even, it returns ‘temp*temp’ (raising ‘a’ to the power of ‘b’)
The code computes ‘func(3, 5)’ and prints the result.

 

Summary

You can read more about Python functions from python.org official documentation.

Leave a Comment