Tower of Hanoi: Recursive Algorithm

Question

Although I have no problem whatsoever understanding recursion, I can't seem to wrap my head around the recursive solution to the Tower of Hanoi problem. Here is the code from Wikipedia:

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

I understand the base case and the concept of breaking the problem into smaller pieces until you are able to move a single disk. However, I can't figure out how the two recursive calls in the non-base case work together. Perhaps someone can help me out? Thanks.

Herrod

That code could be improved by checking for n=0 and doing nothing in that case, to avoid the duplication of the move. – Instrumental

This might help: learneroo.com/modules/71/nodes/402 – Meanwhile

I wrote a blog post on the recursion itself. It goes into some extreme depth and, quite honestly, it takes some time to grasp but once you visualize it, it makes so much more sense. Seriously, save yourself some time and check this out: dima.to/blog/?p=29 – Gorgeous

Actually the basic idea is if we want to solve the problem for N disks then we can re-use the problem with N-1 disks. The Base case is when N = 1. I have tried to explain this in my blog using Java code. krishnalearnings.blogspot.in/2015/06/… – Ponderable

You may try to create a visualization like this: thewalnut.io/visualizer/visualize/1322/342 to see if it helps in understanding... – Strappado

you should check out this answer in - Tower of Hanoi: Recursive Algorithm – Spiegel

Answer 1

Actually, the section from where you took that code offers an explanation as well:

To move n discs from peg A to peg C:

1. move n−1 discs from A to B. This leaves disc #n alone on peg A
2. move disc #n from A to C
3. move n−1 discs from B to C so they sit on disc #n

It's pretty clear that you first have to remove n − 1 discs to get access to the nth one. And that you have to move them first to another peg than where you want the full tower to appear.

The code in your post has three arguments, besides the number of discs: A source peg, a destination peg and a temporary peg on which discs can be stored in between (where every disc with size n − 1 fits).

The recursion happens actually twice, there, once before the writeln, once after. The one before the writeln will move n − 1 discs onto the temporary peg, using the destination peg as temporary storage (the arguments in the recursive call are in different order). After that, the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower, by moving the n − 1 tower from the temp peg to the destination peg, above disc n.

Klausenburg

The only way you can move disc #n from A to C is to do two things: (1) get all the smaller discs off of disc #n (which is still on peg A). (2) make sure peg C is ready to receive disc #n. The only way to do this is to put all those other discs onto peg B so they are out of the way. – Raina

@JasonS I am clear with the 1 and 2 steps, but I couldnt get the 3rd step. Could you please explain for that – Abmho

um... my post was 2 1/2 years ago.... if you mean "The only way to do this is to put all those other discs onto peg B so they are out of the way", you can do that recursively: discs 1 to n are on peg A so any discs on peg B are larger than n. – Raina

@Abmho In my opinion try to visualize the moves with just 2 discs. The pattern exhibited in that transfer, is what we need to repeat again & again. This recursive pattern is followed whenever multiple discs are to be moved between towers. After that visualize 3 disc solution and you'll see that step 3) uses same kind of recursive technique but utilizing the other 2 towers. – Zama

Here is source code in java awesomedsalgo.blogspot.in/2016/07/tower-of-hanoi.html – Doerr

Answer 2

a year ago i had i functional programming course and draw this illustration for the algorithm. hope it helps!

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

The 3 rings problem has been splited to 2 2-rings problem (1.x and 3.x)

Infuse

Answer 3

There's a good explanation of the recursive Hanoi implementation at http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html.

Summary is, if you want to move the bottom plate from stick A to stick B, you first have to move all the smaller plates on top of it from A to C. The second recursive call is then to move the plates you moved to C back onto B after your base case moved the single large plate from A to B.

Anaclitic

Answer 4

I agree this one isn't immediate when you first look at it, but it's fairly simple when you get down to it.

Base case: your tower is of size 1. So you can do it in one move, from source directly to dest.

Recursive case: your tower is of size n > 1. So you move the top tower of size n-1 to an extra peg (by), move the bottom "tower" of size 1 to the destination peg, and move the top tower from by to dest.

So with a simple case, you have a tower of height 2:

 _|_    |     |
__|__   |     |
===== ===== =====

First step: move the top tower of 2-1 (=1) to the extra peg (the middle one, lets say).

  |     |     |
__|__  _|_    |
===== ===== =====

Next: move the bottom disc to the destination:

  |     |     |
  |    _|_  __|__
===== ===== =====

And finally, move the top tower of (2-1)=1 to the destination.

  |     |    _|_
  |     |   __|__
===== ===== =====

If you think about it, even if the tower were 3 or more, there will always be an empty extra peg, or a peg with all larger discs, for the recursion to use when swapping towers around.

Leafstalk

I think the key is,in all recursion problems, we need to think about simple use case first and solve with an algorithm , apply the same to more input.Thanks! – Children

Answer 5

Suppose we want to move a disc from A to C through B then:

1. move a smaller disc to B.
2. move another disc to C.
3. move B to C.
4. move from A to B.
5. move all from C to A.

If you repeat all the above steps, the disc will transfer.

Blackshear

Answer 6

I feel the pain!

Although this is an old post, I think what one really needs to understand, is not the "move this to that" approach but that the answer involves using the side-effect of the recursion.

A invaluable help to me was the "The Little Schemer" which teaches one to think and write recursive functions.

However, this teaches the reader to use the results of the returned result in the next recursive call.

In the Tower of Hanoi, the answer is not in the returned result per se, but in the observation of the returned result.

The magic occurs in the succesive rearrangment of the function parameters.

Yes the problem is really in three parts:

• moving a smaller tower to the spare peg
• moving the last disc to the destination peg
• moving the remaining tower on the spare peg to the destination peg.

In Scheme:

(define (th n a b c)
    (if (zero? n) 'done
        (begin
           (th (- n 1) a c b)
           (display (list a c))
           (newline)
           (th (- n 1) b a c))))
(th 5 'source 'spare 'destination)

However it is the displaying of the function parameters which is the solution to the problem and crucially understanding the double tree like structure of the calls.

The solution also conveys the power of proof by induction and a warm glow to all programmers who have wrestled with conventional control structures.

Incidently, to solve the problem by hand is quite satisfying.

• count the number of discs
• if even, move the first disc to the spare peg, make next legal move (not involving the top disc). Then move the top disc to the destination peg, make the next legal move(nittd). Then move the top disc to the source peg, make the next legal move(nittd)...
• if odd, move the first disc to the destination peg, make the next legal move (not involving the top disc). Then move the top disc to the spare peg, make the next legal move(nittd). Then move the top disc to the source peg, make the next legal move(nittd)...

Best done by always holding the top disc with the same hand and always moving that hand in the same direction.

The final number of moves for n discs is 2^n - 1 the move n disc to destination is halfway through the process.

Lastly, it is funny how explaining a problem to a colleague, your wife/husband or even the dog (even it they not listening) can cement enlightenment.

Oahu

Answer 7

After reading all these explanations I thought I'd weigh in with the method my professor used to explain the Towers of Hanoi recursive solution. Here is the algorithm again with n representing the number of rings, and A, B, C representing the pegs. The first parameter of the function is the number of rings, second parameter represents the source peg, the third is the destination peg, and fourth is the spare peg.

procedure Hanoi(n, A, B, C);
  if n == 1
    move ring n from peg A to peg B
  else
    Hanoi(n-1, A, C, B);
    move ring n-1 from A to C
    Hanoi(n-1, C, B, A);
end;

I was taught in graduate school to never to be ashamed to think small. So, let's look at this algorithm for n = 5. The question to ask yourself first is if I want to move the 5th ring from A to B, where are the other 4 rings? If the 5th ring occupies peg A and we want to move it to peg B, then the other 4 rings can only be on peg C. In the algorithm above the function Hanoi (n-1, A, C, B) is trying to move all those 4 other rings on to peg C, so ring 5 will be able to move from A to B. Following this algorithm we look at n = 4. If ring 4 will be moved from A to C, where are rings 3 and smaller? They can only be on peg B. Next, for n = 3, if ring 3 will be moved from A to B, where are rings 2 and 1? On peg C of course. If you continue to follow this pattern you can visualize what the recursive algorithm is doing. This approach differs from the novice's approach in that it looks at the last disk first and the first disk last.

Raptorial

Answer 8

Here goes the explanation. Look at the picture ->

By calling Movetower(3,a,b,c), you intend to move all the 3 discs from tower A to tower B. So the sequential calls are ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

Hope it helps :)

For Animation : https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

Galengalena

Answer 9

Think of it as a stack with the disks diameter being represented by integers (4,3,2,1) The first recursion call will be called 3 times and thus filling the run-time stack as follows

1. first call : 1. Second call : 2,1. and third call: 3,2,1.

After the first recursion ends, the contents of the run-time stack is popped to the middle pole from largest diameter to smallest (first in last out). Next, disk with diameter 4 is moved to the destination.

The second recursion call is the same as the first with the exception of moving the elements from the middle pole to destination.

Chaschase

Answer 10

The first recursive call moves all the pieces except the biggest one from source to by using dest as the auxilary pile. When done all the pieces except the biggest will lie on by and the biggest one is free. Now you can move the biggest one to dest and use another recursive call to move all the pieces from by to dest.

The recursive calls won't know anything about the biggest piece (i.e. they will ignore it), but that's ok because the recursive calls will only deal with the pieces that are smaller and thus can be moved onto and off the biggest piece freely.

Loach

Answer 11

It's simple. Suppose you want to move from A to C

if there's only one disk, just move it.

If there's more than one disk, do

• move all disks (n-1 disks), except the bottom one from A to B
• move the bottom disk from A to C
• move the n-1 disks from the first step from A to C

Keep in mind that, when moving the n-1 disks, the nth won't be a problem at all (once it is bigger than all the others)

Note that moving the n-1 disks recurs on the same problem again, until n-1 = 1, in which case you'll be on the first if (where you should just move it).

Trimolecular

Answer 12

The answer for the question, how does the program know, that even is "src" to "aux", and odd is "src" to "dst" for the opening move lies in the program. If you break down fist move with 4 discs, then this looks like this:

hanoi(4, "src", "aux", "dst");
if (disc > 0) {
    hanoi(3, 'src', 'dst', 'aux');
        if (disc > 0) {
            hanoi(2, 'src', 'aux', 'dst');
                if (disc > 0) {
                    hanoi(1, 'src', 'dst', 'aux');
                        if (disc > 0) {
                            hanoi(0, 'src', 'aux', 'dst');
                                END
                        document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
                        hanoi(0, 'aux', 'src', 'dst');
                                END
                        }

also the first move with 4 disc(even) goes from Src to Aux.

Eslinger

Answer 13

As some of our friends suggested, I removed previous two answers and I consolidate here.

This gives you the clear understanding.

What the general algorithm is....

Algorithm:

solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination
{
    if(n==0)return;
    solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move
    move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d
    solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call)
}

here is the working example Click here

Cankerous

Answer 14

public static void hanoi(int number, String source, String aux, String dest)
{
    if (number == 1)
    {
        System.out.println(source + " - > "+dest);
    }
    else{
        hanoi(number -1, source, dest, aux);
        hanoi(1, source, aux, dest);
        hanoi(number -1, aux, source, dest);
    }
}

Renown

Answer 15

void TOH(int n, int a, int b){
        /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and  c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
       */
int c = 6-a-b;
if(n==1){
    cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
    // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
    TOH(n-1, a, c);
    // Move the last alone disk from 1st to 3rd stack.
    TOH(1, a, b);
    // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.        
    TOH(n-1, c, b);
}
}
int main() {

TOH(2, 1, 3);
cout<<"FINISHED                        \n";
TOH(3, 1, 3);
cout<<"FINISHED                        \n";
TOH(4, 1, 3);
return 0;
}

Squall

Answer 16

There are three towers namely source tower, destination tower and helper tower. The source tower has all the disks and your target is to move all the disks to the destination tower and make sure in doing so, you never put a larger disk on top of a smaller disk. We can solve this problem using recursion in the steps below:

We have n numbers of disks on source tower

Base case: n=1 If there is only one disk in source tower, move it to destination tower.

Recursive case: n >1

• Move the top n-1 disks from from source tower to helper tower
• Move the only remaining, the nth disk(after step1) to destination tower
• Move the n-1 disks that are in helper tower now, to destination
  tower, using source tower as a helper.

Source code in Java:

private void towersOfHanoi(int n, char source, char destination, char helper) {
    //Base case, If there is only one disk move it direct from source to destination
    if(n==1){
        System.out.println("Move from "+source+" to "+destination);
    }
    else{
        //Step1: Move the top n-1 disks from source to helper
        towersOfHanoi(n-1, source, helper, destination);
        //Step2: Move the nth disk from source to destination
        System.out.println("Move from "+source+" to "+destination);
        /*Step3: Move the n-1 disks(those you moved from source to helper in step1) 
         * from helper to destination, using source(empty after step2) as helper
         */
        towersOfHanoi(n-1, helper, destination, source);
    }
}

Dunford

Answer 17

Just saw this video today: Recursion 'Super Power' (in Python) - Computerphile and I think we should definitely have Professor Thorsten Altenkirch's code in here as its a very beautiful and elegant piece of recursion code and its not always that we have a quality video to show in an answer.

def move(f,t) : 
    print("move disc from {} to {}!".format(f,t))

def hanoi(n,f,h,t) : 
    if n==0 : 
        pass
    else :
        hanoi(n-1,f,t,h)
        move(f,t)
        hanoi(n-1,h,f,t)

our hanoi function has 4 parameters:

• n: number of discs
• f: origin where discs are (from)
• h: intermediate step 'via' (helper)
• t: final position where we want the discs to be in the end (target)

>>> hanoi(4,"A","B","C")
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from A to B!
move disc from C to A!
move disc from C to B!
move disc from A to B!
move disc from A to C!
move disc from B to C!
move disc from B to A!
move disc from C to A!
move disc from B to C!
move disc from A to B!
move disc from A to C!
move disc from B to C!

Spiegel

also... highly recommend people to checkout Computerphile – Spiegel

Answer 18

As a CS student, you might have heard about Mathematical induction. The recursive solution of Tower of Hanoi works analogously - only different part is to really get not lost with B and C as were the full tower ends up.

Nub

Answer 19

In simple sense the idea is to fill another tower among the three defined towers in the same order of discs as present without a larger disc overlapping a small disc at any time during the procedure.

Let 'A' , 'B' and 'C' be three towers. 'A' will be the tower containing 'n' discs initially. 'B' can be used as intermediate tower and 'C' is the target tower.

The algo is as follows:

1. Move n-1 discs from tower 'A' to 'B' using 'C'
2. Move a disc from 'A' to 'C'
3. Move n-1 discs from tower 'B' to 'C' using 'A'

The code is as follows in java:

public class TowerOfHanoi {

public void TOH(int n, int A , int B , int C){
    if (n>0){
        TOH(n-1,A,C,B);
        System.out.println("Move a disk from tower "+A +" to tower " + C);
        TOH(n-1,B,A,C);
    }
}

public static void main(String[] args) {
    new TowerOfHanoi().TOH(3, 1, 2, 3);
}   

}

Motorcycle

Answer 20

Here is my solution code to Towers of Hanoi problem using recursion with golang. `package main

import "fmt"

func main() {
    toi(4, "src", "dest", "swap")
}

func toi(n int, from, to, swap string) {
    if n == 0 {
        return
    }
    if n == 1 {
        fmt.Printf("mov %v %v -> %v\n", n, from, to)
        return
    }
    toi(n-1, from, swap, to)
    fmt.Printf("mov %v %v -> %v\n", n, from, to)
    toi(n-1, swap, to, from)
}`

Centering

Answer 21

This python3 example uses a recursive solution:

# Hanoi towers puzzle
# for each n, you have to move n-1 disks off the n disk onto another peg
# then you move the n disk to a free peg
# then you move the n-1 disks on the other peg back onto the n disk

def hanoi(n):
    if n == 1:
        return 1
    else:
        return hanoi(n-1) + 1 + hanoi(n-1)


for i in range(1, 11):
    print(f"n={i}, moves={hanoi(i)}")

Output:

n=1, moves=1
n=2, moves=3
n=3, moves=7
n=4, moves=15
n=5, moves=31
n=6, moves=63
n=7, moves=127
n=8, moves=255
n=9, moves=511
n=10, moves=1023

But of course the most efficient way to work out how many moves is to realise that the answers are always 1 less than 2^n. So the mathematical solution is 2^n - 1

Submerse

Answer 22

I made a small change to the code here, if you look at the output you can see the small parts pattern are repeating in the parent nodes (Think of it as fractal images)

def moveTower(height,fromPole, toPole, withPole, ar = ''):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole, ar )
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole,height)
        moveTower(height-1,withPole,toPole,fromPole, '*')
    #print(withPole)

def moveDisk(fp,tp,height):
    print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)


moveTower(3,"A","B","C")

And the output is:

 moveTower: 3 A B 
     moveTower: 2 A C 
         moveTower: 1 A B 
             moving disk ~ from A to B
         moving disk ~~ from A to C
         moveTower: 1 B C *
             moving disk ~ from B to C
     moving disk ~~~ from A to B
     moveTower: 2 C B *
         moveTower: 1 C A 
             moving disk ~ from C to A
         moving disk ~~ from C to B
         moveTower: 1 A B *
             moving disk ~ from A to B

Physoclistous

Answer 23

This is code in C++ for Tower of Hanoi, which is recursively called.

#include <iostream>
void toh(int n, char A, char B, char C) {
    if(n == 1) {
        std::cout << "Move Disc 1 from " << A << " to " << C << std::endl;
        return;
    }
    toh(n-1, A, C, B);
    std::cout << "Move Disc " << n << " from " << A << " to " << C <<std::endl;
    toh(n-1, B, A, C);
}
int main() {
    int numberOfDisc;
    char A = 'A', B = 'B', C = 'C';
    std::cout << "Enter the number of disc: ";
    std::cin >> numberOfDisc;
    toh(numberOfDisc,  A, B, C);
    return 0;
}

Moye

Answer 24

I highly recommend this video which illustrates the recursion for this problem in a very understandable way.

The key is to understand the repeating pattern in the solution. The problem can be divided into three main sub-problems. Assuming you have n disks that they are placed at rod A. The target rod is C, and you have B as an intermediate.

Main problem; move n disks from rod A to rod C by using rod B.

1. Move n-1 disks from rod A to rod B by using rod C.
2. Move the last disk from rod A to rod C.
3. Move n-1 disks from rod B to rod C by using rod A.

Sub-problems 1 and 3 are actually solved within the same problem division you see above. Lets take sub problem 1.

Sub-problem 1; move n-1 disks from rod A to rod B by using rod C.

1. Move n-2 disks from rod A to rod C by using rod B.
2. Move the last disk from rod A to rod B.
3. Move n-2 disks from rod C to rod B by using rod A.

We solve the sub-problem in the same way we solve the main-problem. Our base case will be when the number of disks are equal to 1 then we move it from one rod to target one, that's it.

Writing down these steps will help tremendously.

Overword

Answer 25

I actually found a very good explanation for this at https://helloml.org/tower-of-hanoi-recursion/. I recommend you to check it out.

In this article, they have mentioned the steps to solve this problem.

Steps to solve the Tower of Hanoi Problem:

1. Move 'n-1' disks recursively from the source rod to the auxiliary rod.
2. Move the nth disc from source rod to destination rod.
3. Move 'n-1' disks recursively from the auxiliary rod to the destination rod.

It considers a case of three disks and explains the algorithm with a set of images.

Centrality

Answer 26

Tower (N,source,aux.dest):

1.  

   if N =1 Then
      Write : Source -> dest
      return
   end of if
   

2. move N-1 disk from peg source to peg aux

   call Tower (N-1, source, dest, aux)
   

3. write source -> dest

4. move N-1 disks from peg aux to peg dest

   call Tower (N-1, source, dest, aux)
   

5. return

Ragi

Answer 27

/** * */ package com.test.recursion;

/** * @author kamals1986 The Recursive algorithm for Tower of Hanoi Problem The * algorithm grows by power(2,n). */ public class TowerOfHanoi {

private static String SOURCE_PEG = "B";

private static String SPARE_PEG = "C";

private static String TARGET_PEG = "A";

public void listSteps(int n, String source, String target, String spare) {
    if (n == 1) {
        System.out.println("Please move from Peg " + source + "\tTo Peg\t"
                + target);
    } else {
        listSteps(n - 1, source, spare, target);
        listSteps(1, source, target, spare);
        listSteps(n - 1, spare, target, source);
    }
}

public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);

    long endTime = System.currentTimeMillis();

    System.out.println("Done in " + (endTime - startTime) / 1000
            + "\t seconds");
}

}

Nabal

Please explain your answer instead of just posting code on its own. – Volans

Answer 28

def Hanoi(n, A, B, C):
    if(n==1): print "move plates to empty peg"
    else:
       Hanoi(n-1, A, B, C)
       print "move"+str(n)+" to peg "+C
       Hanoi(n-1, B, C, A)

Beanfeast

While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. – Fulton

Answer 29

I am trying to get recursion too.

I found a way i think,

i think of it like a chain of steps(the step isnt constant it may change depending on the previous node)

I have to figure out 2 things:

1. previous node
2. step kind
3. after the step what else before call(this is the argument for the next call

example

factorial

1,2,6,24,120 ......... or

1,2*(1),3*(2*1),4*(3*2*1,5*(4*3*2*1)

step=multiple by last node

after the step what i need to get to the next node,abstract 1

ok

function =

n*f(n-1) 

its 2 steps process
from a-->to step--->b

i hoped this help,just think about 2 thniks,not how to get from node to node,but node-->step-->node

node-->step is the body of the function step-->node is the arguments of the other function

bye:) hope i helped

Ratepayer