PR2EN11: Stack and recursion

Lab materials

Slides: Recursion
Slides: Stack
Examples done together in the lab
- Recursive factorial: https://blue.pri.ee/ttu/files/iax0584/demokood/factorial.c
- Tail-recursive factorial https://blue.pri.ee/ttu/files/iax0584/demokood/factorial_tail.c
- Stack: https://blue.pri.ee/ttu/files/iax0584/demokood/stack_base.c
Alternative example of a stack that uses the SP as a pointer: https://blue.pri.ee/ttu/files/iax0584/demokood/stack_sp_as_pointer.c

Lab tasks

In this lab there are two base tasks, one completely independent advanced task for recursion and one advanced task as an extension to the stack task.

Task 1: Set of recursion tasks

As the first task, you need to create three recursive programs (parts 1, 2 and 3). The task can only be presented once all three are done!

NB! The recursions are extremely simple, avoid looking for solutions on the internet!

In the beginning of the lesson, we’ll create an example of a factorial task solved recursively!

Requirements

You can make the solution as one file with three recursions or as three separate programs. Examples are provided as separate programs.
In all cases, the programs must support positive integers as input. Negative input either has a defined base case or will cause an error.
Input can be asked inside of the application or read as a command line argument.
Iterative solutions are not permitted! All three parts must be solved recursively
Only present your task once all three parts are completed.

Part 1: Sum

Create an application that finds the sum of all positive integers until the entered integer. Negative argument for the recursive function returns the sum as 0 (no positive numbers to add, base case)

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 0
sum(0) = 0
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 1
sum(1) = 1
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 2
sum(2) = 3
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 3
sum(3) = 6
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum -1
sum(-1) = 0

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 0

sum(0) = 0

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 1

sum(1) = 1

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 2

sum(2) = 3

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 3

sum(3) = 6

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum -1

sum(-1) = 0

Part 2: Power

Create an application that allows you to take x to the power of y (x^y). Using the math library and built in power function is not allowed.

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 8
2^8 = 256
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 3
5^3 = 125
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 0
5^0 = 1

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 8

2^8 = 256

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 3

5^3 = 125

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 0

5^0 = 1

NB! Even though you only need to create the solution for positive integers, you can also try to expand to negative values.

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 2
-5^2 = 25
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 3
-5^3 = -125
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -1
2^-1 = 0.5000
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -2
2^-2 = 0.2500
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -3
2^-3 = 0.1250

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 2

-5^2 = 25

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 3

-5^3 = -125

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -1

2^-1 = 0.5000

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -2

2^-2 = 0.2500

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -3

2^-3 = 0.1250

Part 3: Fibonacci sequence

Create an application that finds the n-th Fibonacci number. The fibonacci numbers are calculated as the sum of two previous fibonacci numbers fib_x = fib_{x – 1} + fib_{x – 2}. Compared to the previous recursions, Fibonacci sequence requires two base cases.

Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, …,

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib -1
Error! Input must be 0 or greater!
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 0
fib(0) = 0
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 1
fib(1) = 1
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 6
fib(6) = 8
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 7
fib(7) = 13
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 45
fib(45) = 1134903170

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib -1

Error! Input must be 0 or greater!

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 0

fib(0) = 0

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 1

fib(1) = 1

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 6

fib(6) = 8

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 7

fib(7) = 13

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 45

fib(45) = 1134903170

Did you notice how long it took to find the last value? This is expected in the lab and you don’t need to fix anything, however you should understand why this happened! If not, think or ask!

All 3 parts are done, now present your lab!

You can time the execution of your program using the time program. I’ve put the comparison of two different solutions for Fibonacci below. The second one uses tail-recursion. You can read about it on your own if necessary!

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$  time ./fib 45
fib(45) = 1134903170

real    0m8,520s
user    0m8,518s
sys     0m0,000s
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$  ./fib_tail 45
fib(45) = 1134903170

real    0m0,001s
user    0m0,000s
sys     0m0,001s

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ time ./fib 45

fib(45) = 1134903170

real 0m8,520s

user 0m8,518s

sys 0m0,000s

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib_tail 45

fib(45) = 1134903170

real 0m0,001s

user 0m0,000s

sys 0m0,001s

Task 2: Stack

In this task, we will create a menu program to demonstrate some of the stack functions. The lab task is demonstrative only and is intended to support the dynamic memory allocation studied before – due to the added complexity of this, the benefits of speed are unfortunately diminished.

In the beginning of the lesson, we will create a partial solution with the Push() function.

Requirements

Create a menu structure – the user must be able to select the desired operation.
Create Pop() and Peek() functions
- Pop() removes the topmost element from the stack and returns the value.
- Peek() returns the topmost element from the stack, but does not remove it.
The functions you create are not allowed to display the values themselves! Print the values on the screen once they are returned back to the menu!
NB! In the base variant, you are allowed to reserve a special value to be returned in the case of stack underflow, so that the illegal value wouldn’t be displayed. This is not allowed in the advanced version of this task.
Depending on the function, implement either underflow or overflow detection!
Pay attention to the situation when all the elements are removed from the stack – do not use realloc for 0 bytes, use the free() function!

Debugging function for the stack

In order to get a bit better understanding of the stack contents, we’ll provide a debugging function. In reality, this kind of function goes against the limitations of the stack and may also not even be possible due to the implementation specifics!

void debug_stack(stack st)
{
    printf("DEBUG\n");
    printf("\tStack size: %d\n", st.size);
    printf("\tData pointer: %p\n", st.data);
    
    if (st.size != 0 && st.data == NULL)
    {
        printf("Sanity check failed!\n");
        printf("Stack is NULL, but size is not 0\n");
        return;
    }
    
    if (st.size == 0 && st.data != NULL)
    {
        printf("Sanity check failed!\n");
        printf("Stack data is not NULL, but size is 0\n");
        return;
    }
    
    printf("\tValues: ");
    for (int i = st.size - 1; i >= 0; i--)
    {
        printf("%d ", st.data[i]);
    }
    printf("\n\n");
}

void debug_stack(stack st)

{

printf("DEBUG\n");

printf("\tStack size: %d\n", st.size);

printf("\tData pointer: %p\n", st.data);

if (st.size != 0 && st.data == NULL)

{

printf("Sanity check failed!\n");

printf("Stack is NULL, but size is not 0\n");

return;

}

if (st.size == 0 && st.data != NULL)

{

printf("Sanity check failed!\n");

printf("Stack data is not NULL, but size is 0\n");

return;

}

printf("\tValues: ");

for (int i = st.size - 1; i >= 0; i--)

{

printf("%d ", st.data[i]);

}

printf("\n\n");

}

Testing

During testing, pay extra attention to

stack overflow
stack underflow
freeing the data after last element is popped.
memory leak when the program exits when there are still values in the stack

Click me to see the output

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 0
        Data pointer: (nil)
        Values: 

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 97

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 1
        Data pointer: 0x558cd0c07ac0
        Values: 97 

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 34

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 25

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 99
ERROR: Stack overflow!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 3
        Data pointer: 0x558cd0c07ac0
        Values: 25 34 97 

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
Got 25

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
Got 34

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
Got 97

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
ERROR: Stack underflow!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 0
        Data pointer: (nil)
        Values: 


1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 0

100

101

102

103

104

105

106

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 0

Data pointer: (nil)

Values:

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 1

Data pointer: 0x558cd0c07ac0

Values: 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 34

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 25

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 99

ERROR: Stack overflow!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 3

Data pointer: 0x558cd0c07ac0

Values: 25 34 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

Got 25

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

Got 34

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

Got 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

ERROR: Stack underflow!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 0

Data pointer: (nil)

Values:

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 0

Advanced task 1: practical use case for recursion

This advanced task is given to you as a description of an algorithm. This is a completely independent task, that is not related to the original lab task solution!

NB! The variables in the description are given more to the likes of mathematicians (single letters). Use descriptive variable names when creating your program as is more suited for programming.

Given search key K and an array A of n integers A₀, A₁, … , A_{n – 1} sorted such that A₀ ≤ A₁≤ … ≤ A_{n – 1} use the following algorithm to find if K ∈ A

Set lowIndex L to and highIndex H to n − 1 .
Call the recursive function using 4 arguments – A, L, H, K .
- If L > H , the search terminates as unsuccessful – return 0
- Set m (the position of the middle element) to the floor of (L + H) / 2
- If A_m < K, set L to m + 1 , call recursion again
- If A_m > K, set H to m − 1 , call recursion again
- If A_m = K, the search was successful – return 1

Once the task is complete, prepare the answer to the following questions. Once ready, present your task!

Time complexity – compare the given algorithm and conventional linear search. How many comparisons do you need to find the result from an array that has
- 16 members
- 256 members
- 100 000 members
Give an esimate toe the complexity – e.g. constant, logarithmic, linear, exponential (https://www.bigocheatsheet.com)
If the array wouldn’t be sorted, would the algorithm still work?

Advanced task 2: improving and extending the stack

In this task, we will add a two extra functions and make it a bit more universal than the original solution.

Requirements

Add the following functions to your stack
- Duplicate()
- Swap()
These functions are only allowed to use the original Push(), Pop() and Peek() functions internally to access the stack!
Change your Pop() and Peek() functions in a way that the following would apply
- Stack must allow any integers (reserved values are not allowed!)
- In the case of an underflow during popping from the stack, you can only provide a warning message, but not display the value!
Note: You’ll likely need to adjust your Push() function as well to accomodate the additional functions

Testing

These would be the important edge cases to test for in addition to the normal operation

Pop(), when the stack is empty (do not display any value)

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
ERROR: Stack underflow!

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

ERROR: Stack underflow!

Duplicate(), when the stack is empty
Duplicate(), when the stack is full

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5
ERROR: Stack underflow!
ERROR: Cannot duplicate!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 25

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5
ERROR: Stack overflow!
ERROR: Cannot duplicate!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 3
        Data pointer: 0x561f250ebac0
        Values: 25 25 25

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

ERROR: Stack underflow!

ERROR: Cannot duplicate!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 25

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

ERROR: Stack overflow!

ERROR: Cannot duplicate!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 3

Data pointer: 0x561f250ebac0

Values: 25 25 25

Swap(), when the stack si empty
Swap(), when the stack only has one member

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 4 
ERROR: Stack underflow!
ERROR: Cannot swap!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 2

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 4
ERROR: Stack underflow!
ERROR: Cannot swap !
Original state restored.

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 1
        Data pointer: 0x55e8aa1e6ac0
        Values: 2

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 4

ERROR: Stack underflow!

ERROR: Cannot swap!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 2

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 4

ERROR: Stack underflow!

ERROR: Cannot swap !

Original state restored.

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 1

Data pointer: 0x55e8aa1e6ac0

Values: 2

After this class, you should

Know what a recursion is, including recursive functions and data structures
Know how to write simple recursions
Know about the existence of a tail recursion
Know about the good and bad that recursions bring to the table
Know use cases for recursions
Know what an abstract data structure means
Know what is a stack and what are its properties
Know the use cases for stacks
Know how to create a stack and its mandatory functions

Additional materials

Introduction to Recursion – Data Structure and Algorithm Tutorials
https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/
Merge sort (recursion)
https://www.geeksforgeeks.org/merge-sort/
Quick sort (recursion)
https://www.geeksforgeeks.org/quick-sort/
Stack data structure
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)