Recursion and Stack Frames
How do repetitive actions different in applicative and imperative programming?
Can they have the same efficiency?
Applicative programming can be just as efficient as applicative, especially when looking at recursion.
recursion can almost remove the need for loops
Stack frame: (Stack frames, activation records)
Parameters of a function and their values
Local values
Return point (where to go after returning)
Other (for debugging)
when a function is called - a frame is pushed onto the stack
The stack frame is resolved by passing the return value up and popping the top
The intermediate frames only record successive return values
Code can be written to be contained on one stack frame giving it the same space complexity as something written in a imperative language
Tail : the chronologically last thing a function does
Tail call - a function call that occurs in the tail
Tail recursion - a recursive call that occurs in the tail
Tail recursion are executed in constant stack space similar to a loop in imperative programming
Tail recursion allows for the exclusion of loops
If all function calls occur in the tail, then it can be executed by reusing the same stack frame
If the end of a function before another function is called is the main function again its tail recursion and the same stack frame can be reused
Helper function : a function that does all or part of the work for another function
Functions can have arbitrarily many helper functions
Helper functions must be declared before used
Helper functions can still be tail recursive as long as all calls are tail calls
Internal Helper - Helper functions can be declared within the main function to encapsulate the process of the helper, whilst remaining a tail call
How to write functions to use only 1 frame
To only have 1 frame you must reuse it each time
Use the tail recursion
EXAM: is the function tail recursive ? and/or can you convert a function into tail recursive form