Recursion Handout PDF
Document Details
Tags
Summary
This document provides a detailed overview of recursion, a common programming technique. It explains different types of recursion, including linear, binary, and tail recursion, and illustrates their usage with examples. The document also contrasts recursion with iterative approaches and discusses scenarios where recursion is beneficial. The purpose of the document is to explain different types of recursion and their practical uses.
Full Transcript
IT1815 RECURSION Types of Recursion...
IT1815 RECURSION Types of Recursion Linear recursion – The function calls itself once each time it Fundamentals is invoked. Ex. finding the factorial Recursion is a process where a function calls itself once or multiple times to solve a problem. Any function that calls itself is recursive. Recursion that involves a method directly calling itself is called direct recursion. Indirect recursion occurs when a method invokes another method, eventually resulting in the original method being invoked again. When a recursive function fails to stop recursion, infinite recursion occurs. Output: A recursive algorithm must: o Have a base case – A base case is the condition that allows the algorithm to stop recurring. o Change its state and move toward the base case – A change of state means that some data that the Tail recursion – The function makes a recursive call as its algorithm is using is modified. very last operation. Ex. finding the greatest common divisor o Call itself, recursively. of two (2) non-zero integers Recursion vs. Iteration Iteration is a process of repeating a set of instructions. This is also known as “looping.” Recursion Iteration It terminates when a base It terminates when a condition case is reached. is proven to be false. Each recursive call Each iteration does not requires extra memory require extra memory space. space. An infinite recursion may An infinite loop could loop Output: cause the program to run forever since there is no extra out of memory and may memory being created. result in stack overflow. Solutions to some Iterative solutions to a problems are easier to problem may not always be as formulate recursively. obvious as a recursive solution. 02 Handout 1 *Property of STI [email protected] Page 1 of 2 IT1815 Binary recursion – The function calls itself twice in the run Output: of the function. Ex. Fibonacci series References: Karumanchi, N. (2017). Data structures and algorithms made easy. Hyderabad: CareerMonk Publications. Runestone Academy (n.d.). Citing sources. Retrieved from https://interactivepython.org/runestone/static/pythonds/index.html Output: Mutual recursion – The function works in a pair or a group. Ex. determining whether an integer is even or odd 02 Handout 1 *Property of STI [email protected] Page 2 of 2
