Lab - Recursion

Objectives

• Discuss recursion, tail recursion, and the call stack

Discussion

• Recursion, the call stack, ease of finding solutions to recursively definable problems

• Say we have two functions:

• DrawLine

• DrawSquare

• If we called them such that DrawSquare is called first, followed by DrawLine, we get a call stack that looks like:



• Let's define some terms:

• Stack Frame - Data structure that contains information about a function that has been called and has not yet terminated.

• Stack Pointer - Points to the top of the stack and the function that is currently in-use.

• Return Address - Where to go once function has terminated; the point where the function was called from.

• Locals - simply refers to cariables declared within the function

• Parameters - simply the variables passed to the function when it was called

• Implementation details of the stack are beyond this class' scope, but what we see from here suffices for talking about recursion. We'll talk about two types of recursion:

• Regular Recursion (just Recursion) - Which grows the stack linearly until some base-case is satisfied

• Tail Recursion - Which does not grow the stack

Setup

We need to:

1. Create a directory called recursion_practice in your cs23001 folder

2. Create fibonacci.cpp

Assignment

Fibonacci sequences are a sequence of integers where at each position, n, the value at n is the the two previous values at n - 1 and n - 2. We will use 0 and 1 as the first two digits in this assignment. The sequence would be: 0 1 1 2 3 5 8 13 21 34 etc.... You are to implement the Fibonacci sequence:

• Recursively and Tail Recursively

• So that every number in the sequence is printed

Requirements

The following should be true when you are done, NAMES MUST MATCH EXACTLY:

• In your cs23001 directory you have created a directory named recursion_practice.

• In the directory recursion_practice you have the following files:

• fibonacci.cpp

• There are NO executables in the repository.

• Your program compiles, runs, and performs as specified.

• Your program follows the General Program Requirements.