Sunday, May 21, 2017

Circular Reasoning in Python

When people restate their conclusion as the argument for that same conclusion, it's logical fallacy called circular reasoning. There are some pretty good examples of this on Bo Bennet's blog "Logically Fallacious" including the logical form of it.
Logical Form:
X is true because of Y.
Y is true because of X.,
As someone who tries to be a rational human being, I avoid circular reasoning as often as I can. Yet, I ended up finding it two of the most logically consistent fields: computer science and math. In computer science language, it's called recursion while math's version of circular reasoning is called induction. During my computer science course "CS For All: Introduction to Computer Science and Python Programming" on edX.org by Harvey Mudd, I learned that these two forms of circular reasoning are actually useful problem solving methods even though they seem counter-intuitive at first. An example of recursion from the course's e-book CS For All is this factorial function:

What's going on

This is a function that gives you the factorial of n (aka n!=n*(n-1)*(n-2)...*1). The way this function works is that if n=1, it's obvious that 1! = 1*1 =1 and factorial(1)=1. The tricky part is the 
factorial(n-1) on line 8 which means that in order to get the factorial of a number greater than 1, the factorial function has to use the factorial function. Although it seems that using the factorial function while trying to find the factorial brings you to the same place that you started, it actually helps you solve the problem. At a closer look, you'll see that the inner factorial takes the value of (n-1) which means that the input of inner factorial  is sent back to the first part of the function where it goes through the "if" and "else" clauses and the input decreases by one each time. This loop continues until the input equals one and obviously factorial(1) = 1, so the loop ends and the function returns the value of the variable result after however many loops.

The While Loop 

This method of recursion is actually very similar to a more intuitive concept called the while loop. For example, this is the while loop that I coded to do the exact same thing as the previous function:
Basically, I always start off with a result that equals 1 and the result is multiplied by n until n is no longer greater than 1. With each loop, the n value decreases by 1 so that the function gets the right answer and doesn't continue into infinity. 

Underlying Concepts of Recursion

According to the CS For All textbook, recursion starts with the base case which is the answer to the simplest form of the problem. For the factorial example, the base case is 1!=1 or factorial(1) = 1. From there, the function can solve more complex problems like factorial(34) by putting it through the loop with the input of factorial(n-1) decreasing each time and thus simplifying problem until (n-1)=1. Notice how (n-1) actually gets stored as n with each loop, yet all of the past incarnations of n are multiplied together when it's time to calculate the final result. In a language like Python, variables like n can change value during the course of a program. However, all the values that n ever took are stored in "stacks" which you can think of as these boxes in this figure from CS For All :
As you can see, none of the past versions of n are forgotten and they all enter into the equation for the result. 

Conclusion

Although I still prefer the "while loop", learning recursion has given me a new way to think about solving problems which could be useful in case other methods do not work as well. In addition, seeing the limits of my intuition is a valuable experience for me because I tend to rely on intuition too heavily like many other people. CS For All by Christine Alvarado (UC San Diego), Zachary Dodds (Harvey Mudd), Geoff Kuenning (Harvey Mudd), and Ran Libeskind-Hadas (Harvey Mudd) has been a great guide that helped me understand this strange concept and I would definitely recommend it to anyone else interested in learning more about recursion(see Chapter 2: Function programming) or any other computer science concept. Circular logic can actually be logically valid problem solving method and is definitely not always as bad as this Dilbert cartoon makes it out to be.




No comments:

Post a Comment