What is recursion?

Recursion

In computer science, recursion refers to when a function calls itself in its implementation.

This code will keep calling itself infinitely.

def hio():
	print("hio")
	hio()

hio()

What happens when you run a function? It is placed on a stack and can only be removed once it has finished executing(ran the last line). In this case, we are calling hio2() from hio() (the first function). Therefore, in order for hio() to finish executing and be removed from the stack, hio2() needs to be fully executed.

For better understanding: look at the order of the print statements.

hio tooo

def hio2():
    print("say Hio too")

def hio():
    hio2()
    print("say hio")
    
hio()

Now lets revisit the hio() fucntion calling itself, see how that stack keeps getting filled with out any fucntion getting closure :(

Infinite recursion

There is a problem with the code above, is it will keep running forever. Similar to when you screen share on a video call and your screen ends up sharing the screen being shared.

StackOverflow

Once a function is called, it is placed on a stack for processing. When it is finished running, it is taken off. With a function calling itself, the first function called is never fully executed, so all the preceding functions remain on the stack. Like every other structure, there is limited space on the stack. When functions are getting placed on a stack with out completing, there is an overflow, causing the system to crash. Similar to our favorites sites logo.

How can we stop recursion?

By using if-else statements, we can add a stopping condition inside a function. Or most comanly know as a base condition.

if stopingCondition:
	# Don't call the function recursivly 
else:
	# keep calling the function recursivly 

The stopping condition will be determined by a something changing. In computer science we use a variable to denote change in states of things. If that variable is equal to a certain state, then that can be our stopping condition.

We change the variable each time a function is called, bringing the variable closer to the stopping condition. Once the stopping condition is reached, the function is not called recursively and the program can start taking functions off the stack.

def countdown():
	global n
	if n == 0:
		print("Blastoff!")
	else:
		print(n)
		n -= 1
		countdown()

n = 3
countdown()

Variables can get really messy with each scope. What is another way we can pass the changing information. We can pass as an arrgument of the function and don’t have to worry much about scope of a function. For future problems we will be passing the variable as an arrgument to a fucntion

def countdown(n):
	if n == 0:
		print("Blastoff!")
	else:
		print(n)
		countdown(n-1)

countdown(3)

Returning values vs printing

Once the stopping condition is reached, the function can start returning values and each stack frame can be removed from the call stack. Returning values is only possible when a function is done executing. If there is a return value that has a recursive call, the return statement cannot return until that line has been fully executed. This is only possible when all recursive(n-1) calls have finished running.

def recursive(n)
	# some code
	return n + recursive(n-1)

Same result

def recursive(n)
	# some code
	recursiceCall = recursive() # runs first
	return n + recursiceCall

Line by Line

If there is a return value above a recursive call the recursive call will never be called. If it is below it can only be returned once the all the recurive calls above it or on it have been done. What about a print statement is called as soon as the line in the code is run.

There is a slight caviate: The print statement will never be executed in the case below because the recursive function called before it takes precedence, will only be executed once the function above it has finished running. In this case, print will never be executed because there is no stopping condition in the recursive function.

Let's write a function to print numbers from 1 to N and from N to 1 using the same inputs.

We already have a function that does that for us: countdown(n). The print(n) is executed first, and then the countdown(n-1) is called for execution. We are starting from countdown(3), in the codebefore calling the countdown(2), we print(n) with the value 3 this willl immediatly then we call countdown(2) after. The print(3) has no prior code that needs to be executed so it will be printed immeditaly, as it is not dependent on the recursive call of countdown(n-1).

def countdown(n):
	if n == 0:
		print("Blastoff!")
	else:
		print(n)
		countdown(n-1)

countdown(3)

Is there a way even though unnatrual, we could print from 1 to 3. We know that a line is only run when the lines above it are executed. What will happen if we add the print(n) after the countdown(n-1) function?

def countdown(n):
    if n == 0:
        print("Blastoff!")
    else:
        countdown(n-1)
        print(n)

countdown(3)

The only time the print will be able to run is when all the recursive functions above it have been fully executed. First print will be printed when the base case is hit. That will fully execute countdown(0).

Then it is the turn for countdown(1). countdown(0) is called from inside countdown(1) and countdown(0) is fully executed. The line print(n) with n = 1 can be printed. That will be the first of the numbers to be printed. The order of lines can make all the difference. Arrange them carefully

Let's run a recursive function line by line.

The only thing you need to remember is a line can only be done running when all the code on it and above it are done executing.

A recursive function that adds numbers from 1 to n:

def addNumbers(n):
    if n == 1:
        return 1
    else:
        return n + addNumbers(n-1)
        
addNumbers(5)

This function takes an integer n as input, and returns the sum of all integers from 1 to n.

We will try to add numbers 5 to 1.

The input "n" starts at 5 and is recursively called using the else condition on 4, then 3, then 2, and then 1 putting them all onto the stack, as no line in the code satisfies a stopping condition these functions have not fully run as of yet. The stopping condition will run once n equals 1. The else statements containing the recursive function in addNumbers(1) will not be called.

Once the if condition in addNumbers(1) is executed, and since there will be no recursive calls, the function will completly run. This will allow addNumbers(1) to return a value of 1. This was a precedent which will allow addNumbers(2) to be fully executed, it will reference the completed execution of addNumbers(1) and return the sum by adding the value of n(2) this will complete the execution of addNumbers(2) which will allow addNumbers(3) it to be fully executed by utilizing the return value from addNumbers(2)(which will be 3). This behavior will continue until the execution of addNumbers(5) is complete. Once addNumbers(5) returns to the main program where the function was initially called, we have successfully summed from n to 1 using recursion. That's how, ladies and gentlemen, we utilize recursion to calculate the sum from n to 1.

1 + 2 + 3 + 4 + 5 = 15.

Atleast once more using something called a recursive tree

A recursive tree is a visualization of a recursive function, where each node represents a separate function call and the changing parameters with in the function are displayed within the nodes.

Show Bruno Papa some love 🤍

There is a saying as old as time,

"if it can be done iteratively, it can be done recursively."

In the next module we will learn about the nature of a problem that makes it fit for recursion.