Back

Computer Science Algorithms

Using Recursion

Recursion is when you can define a function in terms of itself, and often allows you to write very elegant, efficient code.

To get started thinking about recursion, let's consider a basic example: a recursive algorithm to count the number of prime numbers less than or equal to \(n,\) which we'll call \(f(n).\) For example, \(f(5) = 3,\) since 2, 3, and 5 are all prime.

First, check if \(n\) is a prime. If so, \(f(n) = 1+f(n-1),\) since there is the prime \(n\) as well as all of the primes up through \(n-1.\) If not, then \(f(n) = f(n-1).\)

By the end of this quiz, you'll see how recursion not only creates more elegant code, but also can be used to speed up runtime.

Using Recursion

Algorithms

Introduction

Intro to Computation

Quiz 1

Using Recursion

Quiz 2

Real-World Application

Quiz 3
           
Continue

Using Recursion

Fill in the recursive step in this function, and then find the answer by evaluating \(10!.\)

Hint: Remember the definition of factorials and use it to relate \(n!\) and \((n-1)!.\) In the code, you will relate factorial(n) and factorial(n-1).

def factorial(n):
    # Solve the base case
    if n == 0 or n == 1:
        return 1
    
    else:
        return # How can you reduce this problem?
    
print(factorial(10))
Python 3
You need to be connected to run code

Using Recursion

Algorithms

Introduction

Intro to Computation

Quiz 1

Using Recursion

Quiz 2

Real-World Application

Quiz 3
           

Using Recursion

Recall that the Fibonacci numbers follow the recursion \(F_n=F_{n−1}+F_{n−2}\) with the initial condition that \(F_1=F_2=1.\) Fill in recursive step in the code outline provided and use it to calculate \(F_{10}.\)

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    
    else:
        return #?

print(fibonacci(10))
Python 3
You need to be connected to run code

Using Recursion

Algorithms

Introduction

Intro to Computation

Quiz 1

Using Recursion

Quiz 2

Real-World Application

Quiz 3
           

Using Recursion

We can now ask ourselves how many arithmetic operations (defined as a single addition, subtraction, multiplication, or division) a recursive implementation requires.

This is easy to calculate for the factorial function. For it, zero operations are required if the input is 1, and an input of \(k\) requires one more operation than an input of \(k-1\). Inducting, this means that we need \(n−1\) operations to compute factorial(n).

How many addition operations are required to calculate fibonacci(10) recursively? You may find the code template helpful in answering this question.

def num_operations_fibonacci(n):
    if n in [1, 2]:
        return 0

    else:
        return #?

print(num_operations_fibonacci(10))
Python 3
You need to be connected to run code

Using Recursion

Algorithms

Introduction

Intro to Computation

Quiz 1

Using Recursion

Quiz 2

Real-World Application

Quiz 3
           

Using Recursion

Feel free to play around in the previous problem with the number of operations it takes to calculate various Fibonacci numbers. For example, it takes 102334154 operations to calculate the 40th Fibonacci number.

A good approximation for the number of operations it takes to calculate the \(n\)th Fibonacci number is \[\frac{1}{2}\left(\frac{1+\sqrt{5}}{2}\right)^n,\] which suggests that it would take approximately \(4.8×10^{208}\) addition operations to calculate the 1000th Fibonacci number.

Suppose you have a super-computer that can do \(10^{15}\) additions per second (which corresponds to the current state of the art). How long would it take for your super-computer to calculate \(F_{1000}?\) 


        

        

            
            
            
            
            
            
            

            

            

            

                
                    
                
                

                

                
                    
                

                
            


            

                

            

            


            

                

                    You need to be connected to run code
                


                

                
                    
                

                
            

        


        

        








    







            


            
        







    

        
            




    
        

            

        

    
    
Using Recursion


    
        

            
        


        

            

                
                

                    
                        
                            

                        
                    
                

                
Algorithms

            

            

                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            
Introduction

        

        

    
        
    


    



                    
                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            

                Intro to Computation
            

        

        
            

                
                
                    
                        Quiz 1
                    
                
            

        

    
        
    


    



                    
                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            

                Using Recursion
            

        

        
            

                
                
                    
                        Quiz 2
                    
                
            

        

    
        
    


    



                    
                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            

                Real-World Application
            

        

        
            

                
                
                    
                        Quiz 3
                    
                
            

        

    
        
    


    



                    
                
            

        

    



            

                
        




    
        
             
        
             
        
             
        
             
        
             
        
             
        
    




        


            

        

        

            
                









    
        
    



    


        

        
    







    
    

    

    

        

        
            
        
            
        
            
        
            
        
            
        

     

    

        
    






    
 

    
    

        

            
                



    
        
                Show explanation
                
        
    


            
        


        



        




    








            
        

    









    
    

    

    

    


    
        
    















            

        
    
        
            

                    






    
    

        

            
                
Using Recursion

            
            

                



    
    
        
        
    
    


    
    



    

        





This algorithm for calculating the \(n^\text{th}\) Fibonacci number is prohibitively expensive! This goes to show that even algorithms that look reasonable at first might be really, really bad ideas.



Consider now a different algorithm called smart_fibonacci. How many additions are necessary to calculate the \(F_{1000}\) with smart_fibonacci(1000)?










        
            
        

        
            
def smart_fibonacci(n):
    a, b = 0, 1
    for i in range(1,n):
        a, b = b, a+b
    return b

print(smart_fibonacci(1000))

        

        

            
            
            
            
            
            
            

            

            
                
            

            

                
                    Python 3
                
                

                

                
                    
                

                
            


            

                

            

            


            

                

                    You need to be connected to run code
                


                

                
                    
                

                
            

        


        

        








    







            


            
        







    

        
            




    
        

            

        

    
    
Using Recursion


    
        

            
        


        

            

                
                

                    
                        
                            

                        
                    
                

                
Algorithms

            

            

                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            
Introduction

        

        

    
        
    


    



                    
                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            

                Intro to Computation
            

        

        
            

                
                
                    
                        Quiz 1
                    
                
            

        

    
        
    


    



                    
                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            

                Using Recursion
            

        

        
            

                
                
                    
                        Quiz 2
                    
                
            

        

    
        
    


    



                    
                
                    
                        





    
    
    
        
            
        
    

        
        
            

        

        
            

                Real-World Application
            

        

        
            

                
                
                    
                        Quiz 3
                    
                
            

        

    
        
    


    



                    
                
            

        

    



            

                
        




    
        
             
        
             
        
             
        
             
        
             
        
             
        
    




        


            

        

        

            
                









    
        
    



    


        

        
    







    
    

    

    

        

        
            
        
            
        
            
        
            
        

     

    

        
    






    
 

    
    

        

            
                



    
        
                Show explanation
                
        
    


            
        


        



        




    








            
        

    









    
    

    

    

    


    
        
    















            

        
    


                            

                        
                    

                

        

    
 


    

    
        

    

    





        







    
        

    


        
    



    

    
        
    

















    


    
        
    
    





    
    
    


    

    
        
    

    
    





    
    

    

    
        
            

    


        
×


        

            
            

            
Problem Loading...

            
Note Loading...

            
Set Loading...