Recursion, Recursion, Recursion …
I’d like to go over some of the basics as it relates to recursion in python. I’ve been moving more and more towards using python 3.X where I can, so this post will be giving examples using version 3.5 of Python. Why use recursion rather than iteration you might be asking? Well, there are a couple of benefits resulting from using recursive programming over an iterative approach. If you are asking what’s the difference here is an example of an iterative approach,
def factorial(num): product = 1 for i in range(num): product *= i + 1 return(product)
And here is an example of a recursive approach.
def factorial(n): if n==0: return 1 # make a calculation and a recursive call f= n* factorial(n-1) return(f)
Notice that the recursive approach calls upon itself whereas the iterative approach is using a for loop to accomplish the same. This is the basis for using any recursive approach, versus iterative where the function usually uses a local variable of control. Both methods can achieve the same end results and for the most part are on equivalence. However, when a problem is using, for example, a linked list where we are trying to ascend the tree there are benefits to using an unbounded method which implements recursion. Recursion algorithms tend to take problems and break them into smaller portions and work on the smaller parts separately from the whole.
Karatsuba Algorithm or is that Kobayashi Maru?
Actually, this is a winning situation. Take for example the process of doing long multiplication by hand. Maybe two 4 digit numbers, as an example below:
1 2 3 4 3 4 5 6 X _______________________ 7 4 0 4 6 1 7 0 0 4 9 3 6 0 0 3 7 0 2 0 0 0 -------------------- 4 2 6 4 7 0 4
In Big(O) annotation this would be the equivalence of O(n^2). Basically meaning that for n values there is a doubling of operations to occur. In 1962 Anatoly Karatsuba published an algorithm that took the longhand form of computation for large numbers being multiplied and identified a way in three step to complete the same operation or in
order of operation. This may not sound like much but, read in the good ol’ Wikipedia if you don’t believe me. Below is a python implementation of this algorithm for your pleasure. By the way, I did not write this implementation myself but wanted to use it as an example, you can find it here in the in Benjamin Baka’s book. I am in no way get anything from the sale of his book, but I’d recommend it if you’re looking to gain more knowledge about data structures and algorithms in whilst using Python. Here is the function below with some commenting for your pleasure.
import math from math import log10 def karatsuba(x, y): # establish the base case for recursion if (x < 10) or (y< 10): return (x*y) # sets n, the number of digits in the highest input number n = max(int(log10(x) + 1), int(log10(y) + 1)) # n_2 rounds up n/2 n2 = int(math.ceil(n/2.0)) # adds 1 if n is uneven n = n if n % 2 == 0 else n + 1 # splits the input numbers a, b = divmod(x, 10**n2) c, d = divmod(y, 10**n2) #applies three recursive steps ac = karatsuba(a, c) bd = karatsuba(b, d) ad_bc = karatsuba((a + b),(c + d)) - ac - bd #perform the final multiplication return ((10**n)*ac) + bd + ((10**n2)* (ad_bc)) print(karatsuba(1234,5678)) print (1234* 5678)
So as you can see this is a method which breaks down the problem into smaller and smaller portions and works on each portion independently before solving. Thanks for reading this post and happy coding!