:PROPERTIES: :ID: 9ff5f281-61c5-4726-9d00-f5b2bd9a0fa8 :mtime: 20231009022341 :ctime: 20231009022233 :END: #+title: Recursion vs Iteration in Programming #+filetags: :public:project: * Recursion vs Iteration in Programming A Recursive program is a program defined in terms of itself. An iterative program is a special type of recursive program which is tail-recursive. * Tail Recursion Tail recursion is when the recursive call of a program is the last call. Tail recursion can be optimized. * Example Here is an example of a recursive, non-iterative function vs an iterative function in Haskell, where we want to compute $1 + 2 + 3 + \cdots + n$. #+BEGIN_SRC haskell recusive_sum :: Int -> Int recursive_sum n = if n == 0 then 0 else n + recursive_sum n - 1 #+END_SRC #+BEGIN_SRC haskell iterative_sum :: Int -> Int -> Int iterative_sum n acc = if n == 0 then 0 else iterative_sum (n - 1) (n + acc) #+END_SRC