Recursion/Tree Recursion: Conceptual Solutions 

ENVIRONMENT DIAGRAM

Draw the environment diagram for the code.

def mystery(n): 
    if n <= 0: 
        return n 
    elif n % 2 == 0 
        return mystery(2 * n -1) 
    else: 
        return mystery(n//2) 
mystery(6)

DEBUGGING

Look at the following versions of the factorial function. Each of them has one bug that is preventing them from working properly. Identify the bug in each example and explain why it’s wrong. DO NOT JUST LOOK AT THE FACTORIAL FROM LECTURE.

def factorial(num): 
    return num * factorial(num - 1) 

There is no base case, or stopping point, so this function will just run forever.

def factorial(num): 
    if num == 1: 
        return 1 
    else: 
        return num * factorial(num) 

The problem is never being made smaller, because each time factorial is called on num again, so this function will also run forever.

def factorial(num): 
    if num == 0: 
        return 0 
    return num * factorial(num - 1)

The base case returns 0, so the final solution will always be multiplied by 0, producing 0 every time it is run.

CODE WRITING

Write a recursive function that sums up all numbers between the given parameter num​ and 0 (kind of like factorial, but instead of multiplication, it uses addition to combine the numbers). Assume ​num​ will never be less than 1.

Write a recursive function that takes in a number, num, and the length of the number, length, and reverses the digits of num.