ChatGPT helps me learn recursion in Python
Recursive joke about recursion goes here
I’m in the middle of working through Replit’s 100 Days of Code course, and this morning I did their unit on recursion. I figured that I’d use this as an opportunity to play with ChatGPT, and see what else I could learn about recursion.
My intuition is that using ChatGPT (or similar tools) is a very scalable and fast way to synthesize and integrate knowledge. I further speculate that you will see the smartest and most talented students increasingly avail themselves of this scalability to quickly synthesize and integrate new knowledge. Though the idea of ChatGPT-based tutors helping less talented students is interesting, I don’t know enough about either ChatGPT, or generative AI technology more generally, or pedagogy to speculate much about this. I simply think that the most talented and most motivated students will quickly seize upon generative AI tools as a highly scalable complement to their efforts to learn new things.
That preamble out of the way, my method here was basically to ask ChatGPT various questions about recursion. Below, you can see my prompts and its output, culminating in a script for calculating permutations of two numbers, n and r, using a recursive function to calculate a factorial.
Substack’s formatting for code is not great, so if what appears below doesn’t make sense to you, or if you find it to be unreadable, you can review a better-formatted version at this Notion page.
Each Prompt/Output section below is demarcated by a section divider, which will hopefully make this more readable. Further, Prompt and Output are rendered in bold.
You will see me iterating on prompts below. Essentially, I’m engineering prompts to get the output I’m looking for. When I first started this exercise I wasn’t sure what practical application of recursion I could come up with. Eventually I seized upon factorials, since factorials are used in calculating permutations. So, you’ll see a prompt asking it to calculate permutations of two variables, n and r. But the subtlety is that I did not specify that ChatGPT ought to return a script which uses recursion to calculate a factorial! Instead, it used Python’s built-in factorial function. Proper prompt engineering requires robust and structured thought, not too dissimilar from code itself.
One final, and critically important, note: some of the code which ChatGPT provides below either does nothing or throws errors. Interestingly, the final code that it generates, which is the most complex, works perfectly! So any student presently relying on ChatGPT to be a scalable and fast tool for integrating and synthesizing new knowledge has to also perform error-checking. This likely would have the beneficent effect of further helping the student synthesize and integrate the knowledge, but my fear is that a lot of student will skip this error-checking part.
Prompt: I want to learn about recursion in python. Can you write a script for me which helps me learn the concept?
Output: Certainly! Here is a simple example of a recursive function in Python that calculates the factorial of a given number:
def factorial(n):
s if n == 1:
return 1
else:
return n * factorial(n - 1)
This function will take an integer n as input and return its factorial. The factorial of a number n is the product of all the integers from 1 to n. For example, the factorial of 4 is 4 * 3 * 2 * 1 = 24.
The key to understanding how this function works is to recognize that it calls itself with a modified version of the original input. Specifically, it calls itself with n - 1. This is what allows the function to perform a calculation on a smaller scale and then combine all of the results to get the final answer.
I hope this helps! Let me know if you have any questions.
Prompt: Great. What’s another example of recursion in python?
Output: Here is another example of a recursive function in Python that calculates the sum of all the elements in a list:
def sum_list(lst):
if not lst: # base case: the list is empty
return 0
else:
return lst[0] + sum_list(lst[1:])
This function will take a list of numbers as input and return the sum of all the elements in the list.
The function works by using the sum_list() function itself to calculate the sum of the elements in the list, except for the first element. It then adds the first element to this result to get the final answer.
For example, if you call sum_list([1, 2, 3]), the function will first calculate the sum of the elements in the list [2, 3], which is 5. It will then add the first element, 1, to this result to get the final answer of 6.
I hope this helps! Let me know if you have any questions.
Prompt: What’s an example of a very complex recursive function in python?
Output: One example of a complex recursive function in Python is a function that calculates the nth number in the Fibonacci sequence. The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, starting from 0 and 1. For example, the first few numbers in the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.
Here is a recursive function that calculates the nth number in the Fibonacci sequence:
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
This function works by calculating the **n - 1**th and **n - 2**th numbers in the Fibonacci sequence and adding them together to get the **n**th number. It does this by calling itself with n - 1 and n - 2 as the input.
For example, if you call fibonacci(5), the function will first calculate the fourth and third numbers in the Fibonacci sequence, which are 2 and 1, respectively. It will then add these numbers together to get the fifth number, which is 3.
I hope this helps! Let me know if you have any questions.
Prompt: How can I use recursion as part of a larger script?
Output: Recursive functions can be used just like any other functions in Python. You can call them from other functions or from the main body of your code, and you can pass them arguments and receive return values just like with any other function.
Here is an example of a script that uses a recursive function to calculate the factorial of a number and prints the result to the console:
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
def main():
number = 5
result = factorial(number)
print(f"The factorial of {number} is {result}.")
if __name__ == '__main__':
main()
This script defines a function factorial() that calculates the factorial of a given number using recursion, and a function main() that calls the factorial() function and prints the result to the console.
The if __name__ == '__main__': block at the bottom is a common idiom in Python that allows you to specify the code that should be executed when the script is run directly. In this case, it calls the main() function when the script is run.
I hope this helps! Let me know if you have any questions.
Prompt: Ok write a script that lets a user calculate permutations, using variables n and r
Output: Certainly! Here is a Python script that allows a user to calculate the number of permutations of size r that can be taken from a set of size n:
def calculate_permutations(n, r):
# Check for valid input
if n < 0 or r < 0:
return "Error: n and r must be non-negative integers."
elif n < r:
return "Error: n must be greater than or equal to r."
# Calculate permutation
result = 1
for i in range(n, n-r, -1):
result *= i
return result
# Test the function
print(calculate_permutations(5, 3)) # Output: 60
print(calculate_permutations(4, 4)) # Output: 24
print(calculate_permutations(4, 0)) # Output: 1
print(calculate_permutations(4, 5)) # Output: "Error: n must be greater than or equal to r."
print(calculate_permutations(-1, 3)) # Output: "Error: n and r must be non-negative integers."
The function first checks that the input is valid (i.e., that n and r are non-negative integers and that n is greater than or equal to r). If the input is invalid, the function returns an error message. If the input is valid, the function calculates the permutation using a loop. It starts at n and iteratively multiplies by the next integer down to n-r+1, which gives the desired result.
I hope this helps! Let me know if you have any questions.
Prompt: Ok re-write this script to make use of the permutation formula: n! / (n - r)!
Output: Certainly! Here is a revised version of the Python script that uses the permutation formula n! / (n - r)! to calculate the number of permutations of size r that can be taken from a set of size n:
def calculate_permutations(n, r):
# Check for valid input
if n < 0 or r < 0:
return "Error: n and r must be non-negative integers."
elif n < r:
return "Error: n must be greater than or equal to r."
# Calculate permutation
result = 1
for i in range(n, n-r, -1):
result *= i
result /= math.factorial(n-r) # Divide by (n-r)!
return result
# Test the function
print(calculate_permutations(5, 3)) # Output: 60
print(calculate_permutations(4, 4)) # Output: 24
print(calculate_permutations(4, 0)) # Output: 1
print(calculate_permutations(4, 5)) # Output: "Error: n must be greater than or equal to r."
print(calculate_permutations(-1, 3)) # Output: "Error: n and r must be non-negative integers."
In this revised version, the function first checks that the input is valid (i.e., that n and r are non-negative integers and that n is greater than or equal to r). If the input is invalid, the function returns an error message. If the input is valid, the function calculates the permutation using the formula n! / (n - r)!. It starts by calculating n! using a loop, then divides by (n-r)! using the math.factorial() function. This gives the desired result.
I hope this helps! Let me know if you have any questions.
Prompt: Ok re-write this script to define the factorial function recursively.
Output: Certainly! Here is a revised version of the Python script that defines a recursive function factorial() to calculate the factorial of a given non-negative integer n:
def factorial(n):
# Check for valid input
if n < 0:
return "Error: n must be a non-negative integer."
# Calculate factorial using recursion
if n == 0:
return 1
else:
return n * factorial(n-1)
def calculate_permutations(n, r):
# Check for valid input
if n < 0 or r < 0:
return "Error: n and r must be non-negative integers."
elif n < r:
return "Error: n must be greater than or equal to r."
# Calculate permutation
result = factorial(n) / factorial(n-r)
return result
# Test the function
print(calculate_permutations(5, 3)) # Output: 60
print(calculate_permutations(4, 4)) # Output: 24
print(calculate_permutations(4, 0)) # Output: 1
print(calculate_permutations(4, 5)) # Output: "Error: n must be greater than or equal to r."
print(calculate_permutations(-1, 3)) # Output: "Error: n and r must be non-negative integers."
In this revised version, the factorial() function is defined to take in a single argument n and return the factorial of n. The function first checks that n is a non-negative integer. If n is negative, the function returns an error message. If n is non-negative, the function uses recursion to calculate the factorial of n. If n is 0, the function returns 1. If n is greater than 0, the function returns n multiplied by the factorial of n-1.
The calculate_permutations() function then uses the factorial() function to calculate the permutation n! / (n - r)!. It first checks that the input is valid (i.e., that n and r are non-negative integers and that n is greater than or equal to r). If the input is invalid, the function returns an error message. If the input is valid, the function calculates the permutation by dividing n! by (n - r)! using the factorial() function.
I hope this helps! Let me know if you have any questions.