[Solved] Recursion When to use it? [closed]

Question

Recursion is the foundation of computation, every possible program can be expressed as a recursive function (in the lambda calculus). Hence, understanding recursion gives you a deeper understanding of the principles of computation.

Second, recursion is also a tool for understanding on the meta level: Lots of proofs over the natural numbers follow a pattern called “natural induction”, which is a special case of structural induction which in turn allows you to understand properties of very complex systems in a relatively simple way.

Finally, it also helps to write good (i.e. readable) algorithms: Whenever there is data to store/handle in a repetitive calculation (i.e. more than incrementing a counter), you can use a recursive function to implicitly manage a stack for you. This is also often very efficient since most systems come with a machine stack at hand.

Accepted Answer

Recursion is the foundation of computation, every possible program can be expressed as a recursive function (in the lambda calculus). Hence, understanding recursion gives you a deeper understanding of the principles of computation.

Second, recursion is also a tool for understanding on the meta level: Lots of proofs over the natural numbers follow a pattern called “natural induction”, which is a special case of structural induction which in turn allows you to understand properties of very complex systems in a relatively simple way.

Finally, it also helps to write good (i.e. readable) algorithms: Whenever there is data to store/handle in a repetitive calculation (i.e. more than incrementing a counter), you can use a recursive function to implicitly manage a stack for you. This is also often very efficient since most systems come with a machine stack at hand.