Recursion Vs Iteration

A piece of code which executes repeatedly based on the different inputs. In general, before solving any large problem first, we need to divide the problem and then you need to solve either using iterative way or recursion way.

Recursion sample:

unsigned long FactorialR(int Num)
{
if (Num == 0)
return(1);
return(Num*FactorialR(Num-1));
}

This function will take ‘Num’ as parameter and executes the same function till it satisfies exit condition i.e ‘Num == 0’.

If we pass 5 as parameter to this function it will execute as following:

  • Num[5]*Factorial(Num-1)[?] -> 5*? it doesn’t return immediately
  • Num[4]*Factorial(Num-1)[?] -> 4*? it doesn’t return immediately
  • Num[3]*Factorial(Num-1)[?] -> 3*? it doesn’t return immediately
  • Num[2]*Factorial(Num-1)[?] -> 2*? it doesn’t return immediately
  • Num[1]*Factorial(Num-1)[?] -> 1*? it doesn’t return immediately

After Num == 0, then it will start returning result of processed result of the function in reverse order like following:

  • Num[1]*Factorial(Num-1)[ 1] -> 1* 1 (1 is returned value of the previous function call)
  • Num[2]*Factorial(Num-1)[ 1] -> 2* 1 (1 is returned value of the previous function call)
  • Num[3]*Factorial(Num-1)[ 2] -> 3* 2 (2 is returned value of the previous function call)
  • Num[4]*Factorial(Num-1)[ 6] -> 4* 6 (6 is returned value of the previous function call)
  • Num[5]*Factorial(Num-1)[24] -> 5*24 (24 is returned value of the previous function call)

Finally, function will return 120 result to the caller.

Iteration sample:

unsigned long FactorialI(int Num)
{
int Result = 1;
for ( ; Num > 0; Num– )
Result = Result * Num ;
return(Result);
}

This function will take ‘Num’ as parameter and executes the same code inside the loop till it satisfies exit condition i.e ‘Num > 0’.

If we pass 5 as parameter to this function it will execute as following:

  • Result * Num -> 1*5 = 5 (5 is stored in ‘Result’ variable)
  • Result * Num -> 5*4 = 20 (20 is stored in ‘Result’ variable)
  • Result * Num -> 20*3 = 60 (60 is stored in ‘Result’ variable)
  • Result * Num -> 60*2 = 120 (120 is stored in ‘Result’ variable)
  • Result * Num -> 120*1 = 120 (120 is stored in ‘Result’ variable)

Finally, function will return 120 result to the caller.

Code generation by compiler for a function

Any function you write, compiler will generate default prolog and epilog for it. So, it will reserve stack for local variable once it enters the function and while leaving the function, it will restore the old value of registers. Layout will look like following by default:

[Prolog]

[Function Body]

[Epilog]

For example:

[Prolog]

push ebp ; Save ebp

mov ebp, esp ; Set stack frame pointer

sub esp, localbytes ; Allocate space for locals

push ; Save registers. will represent list of registers to be saved

Function Body]

[Epilog]

pop ; Restore registers. will represent list of registers to be restored old values

mov esp, ebp ; Restore stack pointer

pop ebp ; Restore ebp

ret ; Return from function

This Epilog and Prolog code generation will vary from compiler to compiler. Microsoft compiler will give option to prevent default code generation of Prolog and Epilog for a given function using a keyword called ‘naked’. This will help you to write your own custom Prolog and Epilog code.

Calling function

When you call any function, first it will push parameter from right to left and then it will push return address before jumping to function. After completing the execution of function, it will jump back to return address which is stored earlier in stack. Normally it will use instruction ‘ret’ or ‘ret ‘where it will transfer control to the address which is found in stack.

For example: TestFunction(10, 30). If you call this function, compiler will generate code like following:

04000000 push 1Eh // 30 == 1Eh

04000002 push 0Ah // 10 == 0Ah

04000004 call TestFunction

04000009

After executing “call TestFunction”. Stack will look like following:

05000005 04  <—–Top of stack

05000004 00

05000003 00  // 04000009h (Stored reverse and this is implementation specific)

05000002 09

05000001 0Ah // 10

05000000 1Eh // 30 <—–Bottom of stack

After completion of function execution, it will transfer control back to caller function. Depends on the calling convention either caller or the calle will clear the stack which is used for parameter pushing.

Iterative Vs Recursion method

Take any kind of problem; you can use either Iterative or Recursion method to solve it. If you can solve using iteration method, same problem can be solved with recursion way and vice versa. But, during solving problem you are going to decide based on following factors:

  1. Does this system have enough stacks?
  2. Which method takes less code i.e. Iterative or Recursive?
  3. Is it possible to solve this problem using Iterative method easily?
  4. Is it possible to solve this problem using Recursion method easily?
  5. Which method is faster i.e. Iterative or Recursive?

If you use Recursion way, compiler will allocate space for variable after entering function and it de-allocate space in stack while leaving the function automatically. This is achieved using Epilog and Prolog code generated by compiler. Recursion function will take some value as parameters and it will process and returns the result (Check above FactorialR() function and also Prolog, Epilog). All the process result will be stored in stack variables till it returns the final result. In Recursion method Prolog and Epilog plays important roles in getting final output. All of the following 3 will contribute to get final result:

[Prolog] /* This will execute once*/

[Function Body] /* This will execute once*/

[Epilog] /* This will execute once*/

If you use Iterative way, compiler will not generate anything automatic code like prolog or epilog for a loop. You are going to store the result during iterative process (a piece of code which is executing inside loop) in stack variables. Once loop exits it will have some expect result. This iterative method will be in”[Function Body]” (check above compiler code generation for a function). In Iterative method Prolog andEpilog will not play any role in getting complete result, it might just store processing result during loop execution. Only function body will be contributed to get final result:

[Function Body] /* This will execute more than once*/

Recursion to Iteration

During converting in this way, we need to create own stack, this stack will store all (it depends) the variable which is created using Prolog code in recursion method. After we use those stack variable then we need to remove from stack which is like Epilog, de-allocating stack variables.

Iteration to Recursion

During converting in this way, we need to analyze, what does we need to store in stack (Prolog), what does processing code should contain (Function Body), this will generally have the code which is executed inside loop and how does stack cleanup happens (Epilog).

For both conversion example check above sample FactorialI() & FactorialR(). Remember, while solving problem as mentioned above you need to consider factors to identify which method is best to solve this problem or else you might solve the problem but in ugly way.

Above sample FactorialI() & FactorialR() are simple to solve. But, to solve complex problems some are easy to think in recursion way some are easy to think using Iterative way. To convert between these 2 methods, you need to visualize how compiler generates code for both Recursion and Iterative method which will make easier for conversion.

For example: You know to solve the problem in recursion way, but in some system where there is less stack you need to maintain your own stack to do the implementation. If you can visualize how compiler does generate code for a function and also if you trace manually, you can convert to manual stack implementation easily.