Recursion vs. Looping in Python

One of the most fundamental tools in programming is a loop. While there are many different types of loops, almost each type of loop has the same basic function: iterating over data to analyze or manipulate it. Recursion is another popular type of function and although it can also analyze and manipulate sequences of data similar to a loop, recursion is probably less understood in many cases, and can often be somewhat confusing. Almost all recursive functions can be re-written as loops, and vice versa. However, each type of function has advantages and disadvantages, and knowing when to use one over the other is something we’ll take a look at here. In the following post, we’re going to try and answer the following questions: What is a For Loop? What is recursion? What is a practical example of each method? When should each of the two methods be used? What are recursive data structures? Let’s start with what often seems to be the more simple of the two methods, looping. For Loops For Loop Flow A for loop is used for iterating over a sequence (that is either a list, a tuple, a dictionary, a set, or a string). A for loop terminates whenever it reaches the end of the sequence of data. Let’s imagine we wanted to add all the numbers below 5, and get the total. Sure, we could simply add 1+2+3+4+5. But if we turn it into a function, it allows us to reuse the same function to add numbers below 10, or 20, or whatever. There could be cases where we would need two values to be added, without knowing what the values were, so having a function that would return the sum of numbers below a certain value could be handy. In this case, we might do something like the following: In order to make this loop work, we would need to have all of the numbers stored as a list so that we could iterate over each element and add it to the total. Let’s look at how this might look in actual code: def getTotal(n):total = 0for number in list(range(n+1)):print numbertotal = total + numberreturn total print getTotal(5) Our function starts by taking in a number as a parameter. Here, we’ll use 5 as our parameter. Then, we’ll set our total equal to 0. Finally, we iterate over a list of numbers between 0 and . We do here, because would give us the numbers less than n, but not including n, which in this case would be 0,1,2,3,4. Since we want to include 5, we will use n+1 n+1 list(range(n)) n+1. If we run this code, we can see that at each iteration, we have the number we expect, and we are returned the total. Our printed output would like like this: 01234515 Recursion Recursion occurs when any function calls itself. One of the big differences between recursion and looping is the way that a recursive function terminates. In the above example, a for loop ends at the end of the sequence it is looping over. However, a recursive function could continue indefinitely since it doesn’t necessarily have a sequence of data. Instead, recursive functions have what is called a base condition. A base condition is one that will terminate the loop if the condition is met. Let’s take the above example and re-write it using recursion.Visually, here’s what this might look like: At each function the the function either calls itself with new inputs, or returns a value. Let’s look at how this might look in actual code as well: def getTotal(n, total):print nif n == 0: # base conditionreturn totalelse:return getTotal(n-1, (total+(n))) print getTotal(5, 0) Here, we can pass in a starting number, and a total variable. When the function is first called, the total is 0 and the number is 5. We check to see if the number is 0. If not, we call the function again…but this time instead of calling it with 0 and 5, we call it with 5–1 and 0+5, and repeat this process until the number is 0, at which time we return the total variable, 15. Calculating Compound Interest with Recursion and Looping As a slightly more difficult exercise, let’s determine the value of a loan or an investment with compounded interest. In order to determine what this value would be, we need 4 things: Duration in Years Interest Rate Number of Times Compounded Per Year Principal Amount The formula for calculating compound interest is as follows: However, this would calculate the entire amount at once. Instead, we’ll want to do it in a loop or with recursion. In that case, our time variable (nt), will actually be handled in iterations. In both methods, we will use each of these numbers as variables, so we can go ahead and declare them, and use the same variables for each method. The variables could be defined this way: durationInYears = 10interestRate = .06compoundedPerYear = 12principalAmount = 4000 — — Compound Interest Calculation with Loop To make the calculation easier in a loop, what we’ll do is first get the total number of times the interest will be compounded. If it is going to be compounded monthly, as we’ve set it to in our variables, and the total number of years is 10, then the result will be 120, or 10*12. Now, we can loop over each number in that range, do the calculation on compounding interest for each iteration, and add that to the principal amount. Here’s what the code might look like: def compoundInterest(principal, compounded, duration, rate):totalCompounded = duration * compoundedfor i in range(1, (totalCompounded+1)):principal = principal*(1+(rate/compounded))return principal print (compoundInterest(principalAmount, compoundedPerYear, durationInYears, interestRate)) The only difference between this, and the more simple example is that we are just doing a few more calculations at each iteration. Instead of a sequence of 5, we are actually iterating over the numbers 1 through 120, representing the total number of times the interest would be compounded. If we log the output, we should get a value of: 7277.58693613 — — Compound Interest Calculation with Recursion In the previous example, our sequence of data is 120, which represents the number of times the principal amount will be compounded. After it reaches the end of the sequence, the loop will terminate. With recursion, we could set it up in a similar way. We could give the function total duration, and basically have two conditions: Condition 1: The Duration is not 0. Do the compounding interest calculation. Add the new iterest to the principal amount. Subtract 1 from the total duration. Call the sub again with the new principal amount and the new duration. Condition 2 (base condition) : Duration is 0. Return the Principal Amount. In our previous recursive example, we start at 5, and terminate the function when it reaches 0. Here, we would do the same thing, but would start at 120 instead. def compoundRecursion(principal, compounded, duration, rate, numberOfRecursions):if numberOfRecursions == 0:totalDuration = compounded * durationelif numberOfRecursions != 0:totalDuration = durationif duration == 0:return principalelse:newDuration = totalDuration - 1amount = principal*(1+(rate/compounded))return compoundRecursion(amount, compounded, newDuration, rate, 1) print (compoundRecursion(principalAmount, compoundedPerYear, durationInYears, interestRate, 0)) Here, We either call the function again, or return the revised principal amount. Each time we call the new function, we call it, but pass in the duration minus 1. When the duration is equal to 0, then we only return the principal amount. When to use recursion Using recursion or loops may depend largely on the language we’re using, or what we intend to solve. For example, in JavaScript, using recursion can result in stack frame errors when a the stack limit is reached before the base condition is met. If that’s the case, a loop may work better. The above example also gives us a great example of when recursion may work far better than a loop. Let’s imagine that instead of keeping track of just the numbers, like we’re doing above, we want to keep track of other data at each compounding interval as well. For example, we may want to take into account how regular payments would affect the life of the loan. We might want to terminate the loop before the sequence ends. If the total number of times that interest on a loan would be compounded is 120, then the length of our list is 120. But, if the loan amount is 0 after only 100 iterations, we have 20 unused and unnecessary list elements hanging out at the end of our list. Further complicating a loop scenario is that the value of the variables like the loan amount depend on the value of the loan amount at the previous iteration. It’s not that this is particularly difficult, but it is messy. Visually, here’s how these problems might look: Recursive Data Structures That’s exactly when recursive data structures come in handy. A data structure is recursive if it can be deﬁned in terms of a smaller version of itself. A list is an example of a recursive data structure. For example, let’s take the following list: Now, let’s make two smaller lists from our original list: If we printed both lists, we would get the following: The reason this is so powerful is that with recursive functions and recursive data structures, we can modify an entire list, or a smaller portion of a larger list all at once. When we were thinking about this problem with looping, we can only change one value at one index at at time. As an example of how to do this, consider the following: if we saved these smaller sections of the larger list, we could then call the same function (recursion) and send it the smaller list ( a recursive data structure). Let’s take a look at how this might work with our previous compounded interest example: def recursiveData(data):# Base Condition ( if principal amount == 0 or if duration == 0) # Else Condition ( recalculate the times compounded, duration & principal amount) print (recursiveData(array)) Our function would basically consist of an if else statement. While it could get more complex if we so desired, we can probably accomplish all we want to do here. Eventually, we want to return the finished data, which will have the loan amount and current payment at each interval that the loan is compounded. Our data output might look like this: [{'times compounded': 0,'duration remaining': 10,'interest rate': .06,'current payment': 100,'compounded per year': 12,'principal amount': 4000},{'times compounded': 1,'duration remaining': 10,'interest rate': .06,'current payment': 100,'compounded per year': 12,'principal amount': 3900}] With this in mind, and also looking back to our examples of smaller lists, here’s how this process will probably look: With each recursive call, we’ll take the first element in the array from the list. We’ll then modify the values of that element, and call the function again, but this time passing it array[:1] and array[1:] as parameters. As we can see, halfway through the list, we should have two lists of the same size, and by the end, we’ll have fully transferred and modified all the elements of the first list, and added them all to the second list. Next, we’ll go step by step to create this this function with actual code. step 1. Create the Array durationInYears = 10compoundedPerYear = 12 array = [{'times compounded': 0,'duration remaining': 10,'interest rate': .06,'current payment': 50,'compounded per year': 12,'principal amount': 4000,'total compounded': compoundedPerYear*durationInYears}]*(compoundedPerYear*durationInYears) At this point, we have an array the length of the total number of times the loan would be compounded. Each element contains the same data, which we will change recursively. Step 2. Create the function & base condition def recursiveData(inputArr, outputArr):if len(inputArr) == 0 or inputArr[-1]['principal amount'] <= 0:return outputArr Again, our base condition covers the two scenarios that we would want to terminate the function with. If either we’ve reached the end of the duration ( ) or we’ve paid off the entire loan ( ). len(inputArr) == 0 inputArr[-1][‘principal amount’] <= 0 Step 3. Create the else statement, and define the current, inputArray & outputArray variables else:current = inputArr[:1][0]inputArrayLength = len(inputArr[1:])outputArray = outputArr At this point, the current element we’re popping off of the is . And our output array is also defined. If we need to access our input array later, we could do so with the variable . inputArr current inputArr Step 4. If the output array length is 0, pop the first element off of the input array, (current) and put it in the output without changing it. if len(outputArray) == 0:outputArray.append(current)return recursiveData(inputArr[1:], outputArray) Now, our two arrays should like like the diagram we saw above, when the recursive function is called initially. step 5. If the output array is greater than 0, modify all the values for our current element. else:newTimesCompounded = outputArray[-1]['times compounded'] + 1newDurationRemaining = current['duration remaining']if ((outputArray[-1]['times compounded'] + 1) % 12) == 0:newDurationRemaining = outputArray[-1]['duration remaining'] - 1principal = (outputArray[-1]['principal amount'])*(1+(outputArray[-1]['interest rate']/outputArray[-1]['compounded per year']))currentPayment = current['current payment']if currentPayment > principal:currentPayment = principalnewPrincipalAmount = (principal - currentPayment)newTotalCompounded = outputArray[-1]['total compounded'] - 1newCurrent = {'times compounded': newTimesCompounded,'duration remaining': newDurationRemaining,'interest rate': current['interest rate'],'current payment': currentPayment,'compounded per year': current['compounded per year'],'principal amount': newPrincipalAmount,'total compounded': newTotalCompounded} At this point, we could print our variable, which is the modified variable, and it would have all the new data after it has been compounded and a payment has been made on the loan. Next, we’ll need to add this variable to our output array. newCurrent current Step 6. Add the new current variable to the output array outputArray.append(newCurrent) Step 7. Call the recursive function with the new parameters return recursiveData(inputArr, outputArray) And we’re done! Let’s take a look at the entire code block in one piece: durationInYears = 10compoundedPerYear = 12 array = [{'times compounded': 0,'duration remaining': 10,'interest rate': .06,'current payment': 2000,'compounded per year': 12,'principal amount': 4000,'total compounded': compoundedPerYear*durationInYears}]*(compoundedPerYear*durationInYears) def recursiveData(inputArr, outputArr):if len(inputArr) == 0 or inputArr[-1]['principal amount'] <= 0:return outputArrelse:current = inputArr[:1][0]inputArrayLength = len(inputArr[1:])outputArray = outputArrif len(outputArray) == 0:outputArray.append(current)return recursiveData(inputArr[1:], outputArray)else:newTimesCompounded = outputArray[-1]['times compounded'] + 1newDurationRemaining = current['duration remaining']if ((outputArray[-1]['times compounded'] + 1) % 12) == 0:newDurationRemaining = outputArray[-1]['duration remaining'] - 1principal = (outputArray[-1]['principal amount'])*(1+(outputArray[-1]['interest rate']/outputArray[-1]['compounded per year']))currentPayment = current['current payment']if currentPayment > principal:currentPayment = principalnewPrincipalAmount = (principal - currentPayment)newTotalCompounded = outputArray[-1]['total compounded'] - 1newCurrent = {'times compounded': newTimesCompounded,'duration remaining': newDurationRemaining,'interest rate': current['interest rate'],'current payment': currentPayment,'compounded per year': current['compounded per year'],'principal amount': newPrincipalAmount,'total compounded': newTotalCompounded}outputArray.append(newCurrent)inputArr = [newCurrent]*inputArrayLengthreturn recursiveData(inputArr, outputArray) returnData = recursiveData(array, [])for i in returnData:print (i) To make sure it’s working the way we want, let’s bump our payment amount up to something really high, to make sure we’re only being returned what we want, and our base condition is being met. If we change the payment amount to 2000, we should get the following data when printed: {'times compounded': 0, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 2000, 'compounded per year': 12, 'principal amount': 4000, 'total compounded': 120} {'times compounded': 1, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 2000, 'compounded per year': 12, 'principal amount': 2019.9999999999995, 'total compounded': 119} {'times compounded': 2, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 2000, 'compounded per year': 12, 'principal amount': 30.099999999999227, 'total compounded': 118} {'times compounded': 3, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 30.25049999999922, 'compounded per year': 12, 'principal amount': 0.0, 'total compounded': 117} Awesome! It seemed to work, and the base condition was met, and returned a much cleaner set of results than we would have gotten otherwise. Think about how annoying it would be if we used a loop to do this, and still had 120 elements to look through, most of which would be useless/empty. In Summary Working with recursion can be daunting at first. But there are some cases where it can be an amazing tool if used correctly. Likewise, loops can also be a better choice, depending on the scenario. Knowing how to do both effectively can be a great tool for the developer tool belt, and also a great way to impress employers in technical interviews.