# Recursion "To understand recursion, one must first understand

Recursion "To understand recursion, one must first understand recursion." -Stephen Hawking What is recursion? Sometimes, the best way to solve a problem is by solving a smaller version of the exact same problem first Recursion is a technique that solves a problem by solving a smaller problem of the

same type Recursion More than programming technique: a way of describing, defining, or specifying things. a way of designing solutions to problems (divide and conquer). Basic Recursion 1. Base cases:

Always have at least one case that can be solved without using recursion. 2. Make progress: Any recursive call must make progress toward a base case. Mathematical Examples Power Function Fibonacci Sequence Factorial Function

Power Function There are recursive definitions for many mathematical problems: The function Power (used to raise the number y to the xth power). Assume x is a non-negative integer: yx = 1, if x is 0 // base case yx = y*y(x-1), otherwise // make progress

Power Function 23 = 2*22 22 = 2*21 21 = 2*20 20 = 1 =2*4=8 =2*2=4 =2*1=2

Fibonacci Sequence Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, Fibonacci Function: Fib(0) = 1 // base case Fib(1) = 1 // base case Fib(n) = Fib(n-1) + Fib(n-2)

Unlike most recursive algorithms: two base cases, not just one two recursive calls, not just one // n>1 Factorial Factorial Function factorial(0) = 1 factorial(n) = n * factorial(n-1) // n

> 0 Compute factorial(3). Factorial Factorial Function factorial(0) = 1 factorial(n) = n * factorial(n-1) // n > Compute factorial(3)

factorial(3) = 3 = = = * 3 3 3 factorial(2)

* ( 2 * factorial(1) ) * ( 2 * ( 1 * factorial(0) ) * ( 2 * ( 1 * 1 ) )) = 6 Coding the Factorial Function Recursive Implementation int factorial(int n)

{ if (n==0) // base case return 1; else return n * factorial(n-1); } Recursive Call Stack Implementing Recursion What happens when a function gets called?

// a method int b(int x) { int z,y; // other statements z = a(x) + y; } return z;

// another method int a(int w) { } return w+w; When a Function is Called Stop executing function b So can return to function b later, need to store

everything about function b Create activation record Includes values of variables x, y, z The place to start executing upon return Push activation record onto the call stack Then, a is bounded to w from b Control is transferred to function a When a Function is Called After function a is executed, the activation

record is popped out off call stack Values of the parameters and variables in function b are restored Return value of function a replaces a(x) in the assignment statement Recursion vs. Iteration Recursion is based upon calling the same function over and over. Iteration simply `jumps back' to the beginning of the loop.

A function call is usually more expensive than a jump. Recursion vs. Iteration Iteration can be used in place of recursion An iterative algorithm uses a looping construct A recursive algorithm uses a branching structure Recursive solutions are often less efficient in terms of both time and space

Recursion may simplify the solution shorter, more easily understood source code Recursion to Iteration Conversion Most recursive algorithms can be translated into iterative algorithms. Sometimes this is very straightforward most compilers detect a special form of recursion, called tail recursion, and translate into iteration automatically.

Sometimes, the translation is more involved May require introducing an explicit stack with which to fake the effect of recursive calls. Coding Factorial Function Iterative implementation int factorial(int n) { int fact = 1; for(int count = 2; count <= n; count++)

fact = fact * count; return fact; } Other Recursive Examples Combinations Euclids Algorithm Binary Search Combinations: n choose k

Given n things, how many different sets of size k can be chosen? n n-1 n-1 = k + k-1 , 1 < k < n (recursive solution) k n n! =

, 1 < k < n (closed-form solution) k k!(n-k)! with base cases: n n = n (k = 1), = 1 (k = n) 1 n

Pascals Triangle Combinations: n choose k int combinations(int n, int k) { if(k == 1) // base case 1 return n; else if (n == k) // base case 2

return 1; else return(combinations(n-1, k) + combinations(n-1, k-1)); } Combinations: Euclid's Algorithm In about 300 BC, Euclid wrote an algorithm to calculate the greatest common divisor (GCD) of two numbers x

and y where (x < y). This can be stated as: 1. Divide y by x with remainder r. 2. Replace y by x, and x with r. 3. Repeat step 1 until r is zero. When this algorithm terminates, y is the highest common factor. GCD(34017, 16966) Euclid's algorithm works as follows: 34,017/16,966 produces a remainder 85

16,966/85 produces a remainder 51 85/51 produces a remainder 34 51/34 produces a remainder 17 34/17 produces a remainder 0 The highest common divisor of 34,017 and 16,966 is 17.

Writing a Recursive Function Determine the base case(s) (the one for which you know the answer) Determine the general case(s) (the one where the problem is expressed as a smaller version of itself) Verify the algorithm (use the "Three-Question-Method")

Three-Question Method 1. The Base-Case Question: Is there a non-recursive way out of the function, and does the routine work correctly for this "base" case? 2. The Smaller-Caller Question: Does each recursive call to the function involve a smaller case of the original problem, leading inescapably to the base case? 3. The General-Case Question: Assuming that the recursive call(s) work correctly, does the whole function work correctly?

Binary Search Search algorithm Finds a target value within a sorted list. Compares target value to the middle element If the two are equal, done. If target less than middle element, search lower half of list. Otherwise, search upper half of list. Continue dividing list in half until find target or run out of list to search.

Efficiency: Runs in at worst logarithmic O(log n) time Takes up linear O(n) space Recursive Binary Search What is the base case(s)? 1. If first > last, return false 2. If item==info[midPoint], return true What is the general case? if item < info[midPoint]

// search the first half if item > info[midPoint], //search the second half Recursive Binary Search boolean binarySearch(Item info[], Item item, int first, int last) { int midPoint; if(first > last) // base case 1 return false;

else { midPoint = (first + last)/2; if(item < info[midPoint]) return BinarySearch(info, item, first, midPoint-1); else if (item == info[midPoint]) { // base case 2 item = info[midPoint]; return true; }

else } } return binarySearch(info, item, midPoint+1, last); When to Use Recursion When the depth of recursive calls is relatively "shallow"

The recursive version does about the same amount of work as the nonrecursive version The recursive version is shorter and simpler than the non-recursive solution Benefits of Recursion Recursive functions are clearer, simpler, shorter, and easier to understand than their non-recursive counterparts. The program directly reflects the abstract solution strategy (algorithm).

Reduces the cost of maintaining the software. Disadvantages of Recursion Makes it easier to write simple and elegant programs, but it also makes it easier to write inefficient ones. Use recursion to ensure correctness, not efficiency. My simple, elegant recursive algorithms are inherently inefficient. Recursion Overhead

Space: Every invocation of a function call requires: space for parameters and local variables space for return address Thus, a recursive algorithm needs space proportional to the number of nested calls to the same function. Recursion Overhead Time:

Calling a function involves allocating, and later releasing, local memory copying values into the local memory for the parameters branching to/returning from the function All contribute to the time overhead.

## Recently Viewed Presentations

• drugs for bugs ?? antibiotics antiviralsa antifungals anti-tubercular antimalarial antihelminthic antimycobacterial antivirals antibiotics commonly known as
• description. A Vacuum tube audio amplifier for which the entire signal path is analog but the audio parameters are digitally controlled via a touch screen graphical user interface which also displays visualizations of the amplitude, frequency and phase characteristics of...
• Israel as Lost Sheep You have not strengthened the weak or healed the sick or bound up the injured. You have not brought back the strays or searched for the lost. You have ruled them harshly and brutally. So they...
• * * * Measuring GDP Expenditures approach GDP = C + I + G + (X-M) Income approach GDP = Compensation of Employees + Gross Operating Surplus + TOPI less Subsidies Production or "value added" approach GDP = Gross Output...
• Graph burning - Anthony Bonato (Kramer,Guillory,Hancock,14): study of emotional or social contagion in Facebook. the underlying network is an essential factor. in-person interaction and nonverbal cues are not necessary for the spread of the contagion.
• tragic flaw) in his/her personality that is taken to an extreme and impairs his/her judgment. *This tragic flaw leads to the hero's/ heroine's own downfall (a . major. catastrophe). *By the end of the play, the tragic hero recognizes his/her...
• Mission. To achieve zero PPM. To provide Total Customer Satisfaction. To become and remain the Preferred Supplier for our OEMs. To be the best in the eyes of our Customers, Employees and all Business Partners of our Organization.
• A bani read at weddings and funerals…for bliss is always around us if we remember Vaheguru. Create an atmosphere for prayer time…. VaheguruJeeKaaKhalsa, VaheguruJeeKeeFateh. ... a Hindu Sadhu (Saint) refused to eat the food served by BhaiAmar Das Jee"as he...