Recursion In C,c++

What is recursion? How does it work? • Recursion is when a function or procedure calls itself. • Mutual recursion is when two or more functions or procedures call each other in a cycle. • A classic example, factorial: /* Returns n!= 1*2*3...(n-1)*n for n >= 0. */ int factorial(int n) { if (n < 2) return 1; else return factorial(n-1) * n; }

Another classic example Fibonacci Numbers /* Returns nth fibonacci number fn for n >= 0: - fn = fn-1 + fn-2 - Base case f0 = 0 and f1 = 1

*/

int fibonacci (int n) { if (n >= 2) { return fibonacci(n-1) + fibonacci(n-2); } else if (n == 1) { return 1; } else { /* n == 0 */ return 0; } }

NOTE: Fibonacci and not F-iobonacci!

Function calls (a picture approach) If A calls B calls C calls D:

A

B

C

passes program control (flow) returns program control (flow)

Each call of routine Y from line L of routine X: • suspends execution of caller X at line L • starts called routine Y at line 1 • returns to caller X line L+1 on exit from called routine Y

D

Picture approach: Factorial int factorial(int n) { if (n < 2) return 1; else return factorial(n-1) * n; }

factorial(3): int factorial (3)

int factorial (2)

factorial (2) 2

int factorial (1)

factorial (1) 1

3 Value returned

Implementation of recursive calls In practice, a recursive call doesn’t make an entire new copy of a routine. Instead, it: • Step 1: records the location to which it will return • Step 2: reenters the new function code at the beginning • Step 3: allocates memory for the local data for this new invocation of the function - For our factorial example, the parameter argument is the only local variable.

Iteration versus Recursion Two implementations of factorial: int fact_re(int n) { if (n < 2) { return 1; else { return fact_re(n-1) * n; } }

int fact_it(int n) { int result = 1; int i; for (i = 1; i <= n; ++i) { result *= i; } return result; }

How many multiplications does each procedure do? What other operations (total computational cost) does each procedure do?

Function call overhead What’s involved when making a function call? • save caller’s state • allocate stack space for arguments • allocate stack space for local variables • invoke routine • at exit (return), release resources • restore caller’s “environment” • resume execution of caller Both the recursive and the iterative routines take time which is proportional to n, but the iterative algorithm will be much faster in most language implementations. However, the recursive is usually more efficient to code!

Combinatorial explosion in Fibonacci fib(5)

= fib(4) + fib(3) = [ fib(3) + fib(2) ] + [ fib(2) + fib(1) ] = [ [ fib(2) + fib(1) ] + [ fib(1) + fib(0) ] ] + [ [ fib(1) + fib(0) ] + 1 ] = [ [ [ fib(1) + fib(0) ] + 1 ] + [ 1 + 0 ] ] + [[1+0]+1] =[[[1+0] +1]+[1+0]]+[[1+0]+1]

Notice that fib(3) is expanded twice, and fib(2) is expanded three times.

Fibonacci by iteration int fibonacci(int n) { int fib0 = 0, fib1 = 1, i, temp; if (n == 0) return fib0; else if (n == 1) return fib1; /* After each iteration, fib0 and fib1 are * the ith and (i-1)st fibonacci numbers for (i = 2; i <= n; ++i) { temp = fib1; fib1 = fib0 + fib1; fib0 = temp; } return fib1; }

Choosing recursion In languages not supporting recursion (e.g. Fortran), recursion can be simulated with the use of a stack. The ‘recursive’ calls are simulated by iteration and “local data” is kept on the stack. Most languages that support recursion use a stack implicitly. This can cause problems in language implementations where this implicit stack has limited size. A recursive implementation is justified when: • it is difficult to write an iterative version, and • the recursion doesn’t solve the same subproblems repeatedly (resulting in a combinatorial explosion) Our next example (Towers of Hanoi) is perfect for recursion.

Towers of Hanoi Goal: Move disks from peg A to peg C. Rule: May only move one disk at a time, onto a smaller disk or an empty peg.

A

B

C

Some initial steps

A

B

C

A

B

C

Breaking the goal into subgoals

A

B

C

A

B

C

Implementation of Towers of Hanoi /* * Prints sequence of moves to move n disks (n >= 0) * from peg source to peg dest using peg inter * as intermediate. */ void move(int n, char source, char dest, char inter) { if (n > 0) { move(n - 1, source, inter, dest); printf(“Move disk from peg %c to peg %c\n”, source, dest); move(n - 1, inter, dest, source); } /* Otherwise n == 0, so do nothing */ }

What is the flow of execution for: char A = ‘A’, B = ‘B’, C = ‘C’; move(3,A,C,B);

Picturing the function calls move(3,A,C,B) move(0,A,B,C)

move(2,A,B,C)

move(1,A,C,B) A to C

move(0,B,C,A) A to B move(1,C,B,A)

move(0,C,A,B)

C to B move(0,A,B,C) move(0,B,C,A)

A to C move(2,B,C,A)

move(1,B,A,C) B to A

move(0,C,A,B) move(0,A,B,C)

B to C move(1,A,C,B) A to C

move(0,B,C,A)

The moves: A to C, A to B, C to B, A to C, B to A, B to C, A to C.

Tail recursion A recursive function is called tail recursive if it only calls itself as a final operation: void f(int a, int b) { int c, d; if (<some_condition>) { /* Not real C */ /* some statements */ f(c, d); /* end with a recursive call */ } else { /* handle base case */ } }

This can always be written without recursion as follows: void f(int a, int b) { int c, d; while (<some_condition>) { /* Not real C */ /* some statements */ a = c; b = d; } /* handle base case */ }