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.

21
1
if num == 1:
return 1
else:
return num + fact_adder(num - 1)

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

def digit_reverse(num, length):
>>> digit_reverse(12345678, 8)
87654321
if num < 10:
return num
else:
return (num % 10) * (10 ** (length - 1)) + digit_reverse(num // 10)