In both cases, the latest increases were the weakest for just over two years, amid reports from panellists of fragile employer confidence.
Although job vacancies continued to rise in September, the rate of growth eased further. Overall demand for staff increased at the slowest pace since October 2009. Weaker expansions of demand were signalled for both permanent and temporary/contract workers.
The rate of inflation of permanent staff salaries quickened in September, but remained well below the average recorded throughout the survey's 14-year history. Hourly temp pay rates increased modestly on the month.
The availability of permanent candidates improved for an eighth successive month in September, and at the sharpest rate since December 2009. Growth of short-term staff availability picked up to a seven-month high.
Kevin Green, chief executive of the REC, said: "Employers are being very cautious about hiring at the moment. This has been exacerbated by weak consumer confidence which leads to people staying in their current role rather than changing jobs. The private sector is still producing new jobs but not in the quantity needed to offset the job losses in the public sector. These factors combined have resulted in the slowest increases in both permanent and temporary billings since August 2009. It's vital that we look at ways to boost these numbers, particularly for young people who continue to be disproportionately affected by unemployment.
"To combat this, the REC is urging the Chancellor to introduce a National Insurance holiday for at least a year to encourage SMEs to take on young people. This is becoming even more critical because as from last Saturday, employers can no longer force older workers to retire at 65. While it is important that mature workers can continue to contribute to the workforce, it means even fewer roles will be available to younger candidates so efforts must be made to incentivise businesses to create jobs.
"We are also calling on the Bank of England Monetary Committee to resume quantitative easing when it meets this week as the economy now needs all the help it can get to kick start growth."
Bernard Brown, partner and head of business services at KPMG, added:"This latest data suggests that surely it's only a matter of time now before we move from a growth position to one of a contracting jobs market.
"September saw rates of growth decline to the weakest for just over two years in both permanent and temporary appointments.
"And although there is still some slight growth, continuing a period of 26 consecutive month-on-month increases in appointments, the rate is slowing.
"The employment agencies surveyed reported that the slower expansion of placements was linked to a lack of confidence among clients over the economic outlook. These macroeconomic concerns and the general downward direction of the growth rate, suggests that we could see it cross the line and move into decline in the near future.
"Looking at sectors: nursing/medical care and the hotel and catering sectors are already in decline, showing weaker demand in September than the previous month. The accounting/financial sector was virtually flat but the others showed some growth."