loading...

Recursive v Iterative Function

erikkristoferanderson profile image Erik Kristofer Anderson ・3 min read

This is based on a lesson I studied in the course Introduction to Computer Science and Programming Using Python on Edx. It's about iterative vs. recursive functions.
The difference, as well as I understand it, is that an iterative executes a few lines of code repeatedly until a condition is met while a recursive function calls itself repeatedly until a certain condition is met.
In this example I will use one of each to calculate a simple power function (result = base^ex), but instead of using Python's built in exponent function (**), these functions will calculate the result by multiplying the base times itself exp times.
It is, I admit, redundant and maybe not very useful, but this is a learning exercise.

I'll start with the iterative example. Code first, then I'll make some observations.

def iterPower(base, exp):
    '''
    base: int or float.
    exp: int >= 0

    returns: int or float, base^exp
    '''
    result = 1
    i=exp
    while i > 0:
        result = result * base
        i -= 1
    return result         

I used a while loop with the condition that it executes while an index, i, is greater than zero. This index starts with the value of the exponent, which is equal to the number of times base needs to be multiplied by itself. On each execution of the loop, exp counts down by one and the variable result gets multiplied by the base.
I set the starting value of result to 1 for two reasons. First, if the exp input is equal to 0, the while loop won't execute and we need a way for the function to return the correct answer, 1. Also, setting result to 1 initializes the variable result so that it can be multiplied by base in the while loop.
The function then returns result.

TLDR: The while loop allows base to be multiplied by itself exp times.

Next the recursive example:

def recurPower(base, exp):

    '''
    base: int or float.
    exp: int >= 0

    returns: int or float, base^exp
    '''

    if exp == 0:
        return 1
    else:
        return base * recurPower(base,exp-1)

This time the repetitions of multiplying the base by itself are achieved by calling the function recurPower within itself. Each time the program gets called, the variable exp decreases by one before being fed into the next instance of the function.
The tunnel of functions within functions reaches its end when exp is equal to zero.
Note that if the input exp is equal to zero, the function just returns 1 and doesn't execute it self at all.
I think this version is cleaner to read, but a little bit harder to understand at first. It's tricky to keep track, in your head, of multiple instances of a function being called within each other.

Well, I hope you learned something. I certainly did as I wrote this.

P.S. I'm new to this community and I'm glad it's a place where I feel comfortable taking a risk by 1. writing about a subject I'm just beginning to learn, and 2. writing something that's a pretty basic example.

P.P.S. This is my first time publishing in markdown, and I LIKE it. It was easy and the output looks really pretty.

Posted on by:

erikkristoferanderson profile

Erik Kristofer Anderson

@erikkristoferanderson

Former Chemist , Current Student , Future Data Engineer

Discussion

markdown guide