recursion and higher order

recursion

programming technique where you create a function to solve a complex problem, calling itself with smaller/simpler input using a base case and recursive case.

base case

simplest possible input where the answer is known directly and doesn’t need any more recursive calls

recursive case

part of recursion where the function is broken down into smaller instances and calls itself

purpose of recursion; why preferred over while/for loops

• some data structures like folders are naturally recursive since they contain files/other folders and trying to track these structures iteratively with loops is error prone

• sorting problems or searching pathways are clearer when expressed recursively

how does recursion work internally?

when a function is called, python pauses the current execution and pushes a stack frame(data block) onto the call stack which stores the function’s local variables and parameters. each recursive call results in a new stack frame, with its own local copy of parameters. when a base case is triggered, the topmost frame returns a value and is taken off the stack, and the program unwinds down to the initial call.

what happens in the case of infinite recursion?

it pushes stack frames indefinitely, but since memory is finite, python reaches its safety ceiling and raises a recursion error saying that maximum recursion depth has been exceeded

if a local variable changes in a recursive call, does it change for all previous calls?

no, each frame isolates its own variables

what does doing number//10 do

chops off the last digit off number

what does [1:] do

cuts off the first digit in a list

higher order function

a function that either accepts one or more functions as an argument, or returns a function as an output

purpose of higher order functions

functions are “first class citizens”(have no restrictions and can be treated as standard values like ints and strings) and higher order functions result in more generic, dynamic code blocks that adjust themselves based off the input(instead of you having to manually code for each input)

lambda functions

created without names(anonymous) and is meant to be used where it is created(throwaway), for single brief tasks(isn’t intended to be re-used) and is deleted after the line runs

what is the syntax for a lambda function

lambda [parameters]: [expression]; cannot contain loops or action statements like print

when are lambdas typically used? what is their purpose

passed as arguments inside higher-order functions, keeps code clean and concise

function factories, and closure

functions that generate and return new customized functions dynamically, based on given arguments. with closure, when an inner function is defined inside an outer function, it holds onto the outer functions variables even after the outer function has been executed and is removed from the call stack.