CS21 Lab 10: Recursion stack frame solutions

Program 1

Provide the base case, recursive case, final output, and draw the stack diagram for the program shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 def show(lst):
    if len(lst) == 0:
        print("done")
    else:
        print(lst[0])
        show(lst[1:])

def main():
    nums = [1, 5, 2, 8]
    show(nums)

main()

The base case occurs when len(lst) == 0
The recursive case is when len(lst) != 0
The final output is below:
```
1
5
2
8
done
```

The stack diagram, shown before the base case of show returns is below:

The stack frame solution above shows how elements of the original list are actually shared when you slice the list. Although correct, this may make things more confusing for you to understand. Therefore, the following alternate stack diagram is also acceptable:

Program 1a

Before you go on, check your understanding! What would happen if we swapped lines 5 and 6 in the program above so that it looked like the program shown below? You only need to provide the output, not the stack diagram.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12 def show(lst):
    if len(lst) == 0:
        print("done")
    else:
        show(lst[1:]) # these two lines were swapped
        print(lst[0]) # from Program 1 shown above

def main():
    nums = [1, 5, 2, 8]
    show(nums)

main()

The final output is below:

done
8
2
5
1

Program 2

Provide the base case, recursive case, final output, and draw the stack diagram for the program shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13 def mystery(a, b):
    if b == 0:
        return 0
    else:
        p = mystery(a, b - 1)
        q = a + p
        return q

def main():
    v = mystery(2, 4)
    print(v)

main()

The base case occurs when b == 0
The recursive case is when b != 0
The final output is 8

The stack diagram, shown before the base case of mystery returns is below:

Program 3

Provide the base case, recursive case, final output, and draw the stack diagram for the program shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11 def dub(s):
    if s == "":
        return s
    else:
        return s[0] + s[0] + dub(s[1:])

def main():
    r = dub("swat")
    print(r)

main()

The base case occurs when s == ""
The recursive case is when s != ""
The final output is sswwaatt

The stack diagram, shown before the base case of dub returns is below: