Recursion Fall 2008RecursionSlide 3Simple ExampleRecursive RoutineRecursive Routines (some facts)ExamplesSlide 8RecursionFall 2008 Dr. David A. [email protected]“This is the song that never ends, Yes it goes on and on my friend. Some people started singing it, not knowing what it was, And they'll continue singing it forever just because -> ” Written and composed by Norman MartinRecursion•A program or function that has the ability to call itself is said to be recursive. •Mathematically, recursion is very interesting and has been around for quite some time. –Take the Fibonacci numbers. A Fibonacci number is the sum of the two previous numbersfn = fn-1 + fn-2•Recursion is very useful in traversing tree structuresSimple Example#include <iostream>using namespace std;int SubtractOnetoZeroint main(void){ int x=10; cout << “final number is “ << << SubtractOnetoZero(x) << endl; return 0;}int SubtractOnetoZero(int x) { if(x==1) return 0; else return SubtractOnetoZero(x-1);}Recursive Routine•A recursive routine will be one that has at least one function call in it to itself. •To behave properly, the routine must have some method to stop the recursion.•There is almost always some type of parameter passed. •Recursive routines almost always return some type other than void.Recursive Routines(some facts)•Not used often except in data structure tree traversal. •any problem that can be coded with a recursive routine can be done interatively with a loop•Recursive functions are easier to write•Recursive functions are usually smaller•Recursive functions have much more overhead because of function calls. •Iterative routines are usually more efficient in the amount of memory used. •Iterative routines usually run more efficientlyExamples// Recursive Fibonnaci functionint Fiv (int n){ if (n<= 0) return 0; else if (n==1) return 1; else return Fib (n-1) + Fib (n-2);}Examples// Iterative Fibonnaci functionint Fib(int n) { int n1=1, n2=2, n3; int i=2; while (I < n); { n3=n1+n2; n1=n2; n2=n3; i++; } return
View Full Document
Unlocking...